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.

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, December). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Presented at 39th International Workshop, WG 2013, 19-21 June 2013

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 39th International Workshop, WG 2013
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 15, 2015
• Print ISSN: 0302-9743
• 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