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

Christophe Crespelle 1, * Philippe Gambette 2
* Corresponding author
1 ComplexNetworks
LIP6 - Laboratoire d'Informatique de Paris 6
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
IWOCA'09: 20th International Workshop on Combinatorial Algorithms, Jun 2009, Hradec nad Moravicí, Czech Republic. Springer Berlin / Heidelberg, 5874, pp.146-157, 2009, Lecture Notes in Computer Science. 〈http://graphs.vsb.cz/iwoca2009/〉. 〈10.1007/978-3-642-10217-2_17〉
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00415935
Contributor : Philippe Gambette <>
Submitted on : Friday, September 11, 2009 - 2:50:03 PM
Last modification on : Thursday, October 26, 2017 - 1:44:08 PM
Document(s) archivé(s) le : Tuesday, October 16, 2012 - 10:50:42 AM

File

2009CrespelleGambette.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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. Springer Berlin / Heidelberg, 5874, pp.146-157, 2009, Lecture Notes in Computer Science. 〈http://graphs.vsb.cz/iwoca2009/〉. 〈10.1007/978-3-642-10217-2_17〉. 〈lirmm-00415935〉

Share

Metrics

Record views

350

Files downloads

656