Efficient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

Efficient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search

Christophe Crespelle
  • Function : Correspondent author
  • PersonId : 863155

Connectez-vous pour contacter l'auteur

Abstract

In this paper we address the problem of designing O(n) space representations for permutation and interval graphs that provide the neighborhood of any vertex in O(d) time, where d is its degree. To that purpose, we introduce a new parameter, called linearity, that would solve the problem if bounded for the two classes. Surprisingly, we show that it is not. Nevertheless, we design representations with the desired property for the two classes, and we implement the Breadth-First Search algorithm in O(n) time for permutation graphs; thereby lowering the complexity of All Pairs Shortest Paths and Single Source Shortest Path problems for the class.
Fichier principal
Vignette du fichier
2009CrespelleGambette.pdf (306.76 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00415935 , version 1 (11-09-2009)

Identifiers

Cite

Christophe Crespelle, Philippe Gambette. Efficient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search. IWOCA'09: 20th International Workshop on Combinatorial Algorithms, Jun 2009, Hradec nad Moravicí, Czech Republic. pp.146-157, ⟨10.1007/978-3-642-10217-2_17⟩. ⟨lirmm-00415935⟩
384 View
651 Download

Altmetric

Share

Gmail Facebook X LinkedIn More