HAL: lirmm-00415935, version 1

DOI: 10.1007/978-3-642-10217-2_17

Detailed view

Export this paper BibTeX - EndNote - TEI - RefWorks -

IWOCA'09: 20th International Workshop on Combinatorial Algorithms, Hradec nad Moravicí : Czech Republic (2009)

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

Christophe Crespelle (  Corresponding author ) 1, Philippe Gambette 2

(2009)

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.

1:	Laboratoire d'Informatique de Paris 6 (LIP6)
	CNRS : UMR7606 – Université Paris VI - Pierre et Marie Curie
2:	Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
	CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc

Research Team: [INFO/ALGCO]

Subject

:

Computer Science/Data Structures and Algorithms Computer Science/Discrete Mathematics

Keywords: algorithmics – compact graph encoding – interval graphs – permutation graphs – Breadth First Search – closed linearity

lirmm-00415935, version 1

http://hal-lirmm.ccsd.cnrs.fr/lirmm-00415935

oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00415935

From: Algo Ligm <>

Submitted on: Friday, 11 September 2009 14:50:03

Updated on: Wednesday, 20 January 2010 09:21:44