Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

Haitze J. Broersma; Jiri Fiala; Petr A. Golovach; Tomas Kaiser; Daniël Paulusma; Andrzej Proskurowski

doi:10.1007/978-3-642-45043-3_12

Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

Haitze J. Broersma
, Jiri Fiala
, Petr A. Golovach
, Tomas Kaiser
, Daniël Paulusma
, Andrzej Proskurowski

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

6 Downloads (Pure)

Abstract

We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the O(n^3) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(n + m) time.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers
Editors	Andreas Brandstädt, Klaus Jansen, Rüdiger Reischuk
Place of Publication	Berlin
Publisher	Springer
Pages	127-138
Number of pages	12
ISBN (Electronic)	978-3-642-45043-3
ISBN (Print)	978-3-642-45042-6
DOIs	https://doi.org/10.1007/978-3-642-45043-3_12
Publication status	Published - 2013
Event	39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 - Lübeck, Germany Duration: 19 Jun 2013 → 21 Jun 2013 Conference number: 39

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	8165
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013
Abbreviated title	WG
Country/Territory	Germany
City	Lübeck
Period	19/06/13 → 21/06/13

Keywords

MSC-05C
EWI-24425
IR-89270
METIS-302692
Hamilton-connectivity
Linear algorithm
Scattering number
Interval graph

Access to Document

10.1007/978-3-642-45043-3_12

Cite this

Broersma, H. J., Fiala, J., Golovach, P. A., Kaiser, T., Paulusma, D., & Proskurowski, A. (2013). Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers (pp. 127-138). (Lecture Notes in Computer Science; Vol. 8165). Springer. https://doi.org/10.1007/978-3-642-45043-3_12

Broersma, Haitze J. ; Fiala, Jiri ; Golovach, Petr A. et al. / Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. editor / Andreas Brandstädt ; Klaus Jansen ; Rüdiger Reischuk. Berlin : Springer, 2013. pp. 127-138 (Lecture Notes in Computer Science).

@inproceedings{97852a947a3043e88b3e81134ef5be81,

title = "Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs",

abstract = "We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the O(n\textasciicircum{}3) time bound of Kratsch, Kloks and M{\"u}ller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(n + m) time.",

keywords = "MSC-05C, EWI-24425, IR-89270, METIS-302692, Hamilton-connectivity, Linear algorithm, Scattering number, Interval graph",

author = "Broersma, \{Haitze J.\} and Jiri Fiala and Golovach, \{Petr A.\} and Tomas Kaiser and Dani{\"e}l Paulusma and Andrzej Proskurowski",

note = "10.1007/978-3-642-45043-3\_12 ; 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, WG ; Conference date: 19-06-2013 Through 21-06-2013",

year = "2013",

doi = "10.1007/978-3-642-45043-3\_12",

language = "English",

isbn = "978-3-642-45042-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "127--138",

editor = "Andreas Brandst{\"a}dt and Klaus Jansen and R{\"u}diger Reischuk",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

}

Broersma, HJ, Fiala, J, Golovach, PA, Kaiser, T, Paulusma, D & Proskurowski, A 2013, Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. in A Brandstädt, K Jansen & R Reischuk (eds), Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. Lecture Notes in Computer Science, vol. 8165, Springer, Berlin, pp. 127-138, 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, Lübeck, Germany, 19/06/13. https://doi.org/10.1007/978-3-642-45043-3_12

Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. / Broersma, Haitze J.; Fiala, Jiri; Golovach, Petr A. et al.
Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. ed. / Andreas Brandstädt; Klaus Jansen; Rüdiger Reischuk. Berlin: Springer, 2013. p. 127-138 (Lecture Notes in Computer Science; Vol. 8165).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

AU - Broersma, Haitze J.

AU - Fiala, Jiri

AU - Golovach, Petr A.

AU - Kaiser, Tomas

AU - Paulusma, Daniël

AU - Proskurowski, Andrzej

N1 - Conference code: 39

PY - 2013

Y1 - 2013

N2 - We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the O(n^3) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(n + m) time.

AB - We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the O(n^3) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(n + m) time.

KW - MSC-05C

KW - EWI-24425

KW - IR-89270

KW - METIS-302692

KW - Hamilton-connectivity

KW - Linear algorithm

KW - Scattering number

KW - Interval graph

U2 - 10.1007/978-3-642-45043-3_12

DO - 10.1007/978-3-642-45043-3_12

M3 - Conference contribution

SN - 978-3-642-45042-6

T3 - Lecture Notes in Computer Science

SP - 127

EP - 138

BT - Graph-Theoretic Concepts in Computer Science

A2 - Brandstädt, Andreas

A2 - Jansen, Klaus

A2 - Reischuk, Rüdiger

PB - Springer

CY - Berlin

T2 - 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013

Y2 - 19 June 2013 through 21 June 2013

ER -

Broersma HJ, Fiala J, Golovach PA, Kaiser T, Paulusma D, Proskurowski A. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. In Brandstädt A, Jansen K, Reischuk R, editors, Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. Berlin: Springer. 2013. p. 127-138. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-45043-3_12

Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this