Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Broersma, H. J.; Fiala, J.; Golovach, P. A.; Kaiser, T.; Paulusma, D.; Proskurowski, A.

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

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Broersma, H. J.; Fiala, J.; Golovach, P. A.; Kaiser, T.; Paulusma, D.; Proskurowski, A.

Authors

H. J. Broersma

J. Fiala

P. A. Golovach

T. Kaiser

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

A. Proskurowski

Contributors

Andreas Brandstädt
Editor

Klaus Jansen
Editor

Rüdige Reischuk
Editor

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.

Citation

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, 19-21 June 2013, Lübeck, Germany ; revised papers (127-138). https://doi.org/10.1007/978-3-642-45043-3_12

Conference Name	39th International Workshop, WG 2013
Conference Location	19-21 June 2013
Publication Date	Jan 1, 2013
Deposit Date	Dec 20, 2014
Publicly Available Date	Jan 15, 2015
Pages	127-138
Series Title	Lecture notes in computer science
Series Number	8165
Series ISSN	0302-9743,1611-3349
Book Title	Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers.
DOI	https://doi.org/10.1007/978-3-642-45043-3_12
Public URL	https://durham-repository.worktribe.com/output/1153980
Additional Information	19-21 June 2013