Skip to main content

Research Repository

Advanced Search

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.

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


Authors

H.J. Broersma

J. Fiala

P.A. Golovach

T. Kaiser

A. Proskurowski



Abstract

We prove that for all inline image an interval graph is inline image-Hamilton-connected if and only if its scattering number is at most k. This complements a previously known fact that an interval graph has a nonnegative scattering number if and only if it contains a Hamilton cycle, as well as a characterization of interval graphs with positive scattering numbers in terms of the minimum size of a path cover. We also give an inline image time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the previously best-known inline image time bound for solving this problem. As a consequence of our two results, the maximum k for which an interval graph is k-Hamilton-connected can be computed in inline image time.

Citation

Broersma, H., Fiala, J., Golovach, P., Kaiser, T., Paulusma, D., & Proskurowski, A. (2015). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory, 79(4), 282-299. https://doi.org/10.1002/jgt.21832

Journal Article Type Article
Online Publication Date Oct 28, 2014
Publication Date Aug 1, 2015
Deposit Date Dec 20, 2014
Publicly Available Date Mar 29, 2024
Journal Journal of Graph Theory
Print ISSN 0364-9024
Electronic ISSN 1097-0118
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 79
Issue 4
Pages 282-299
DOI https://doi.org/10.1002/jgt.21832
Public URL https://durham-repository.worktribe.com/output/1439478

Files

Accepted Journal Article (415 Kb)
PDF

Copyright Statement
Broersma, H.J. and Fiala, J. and Golovach, P.A. and Kaiser, T. and Paulusma, D. and Proskurowski, A. (2014) 'Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs.', Journal of graph theory, 79(4): 282-299, which has been published in final form at http://dx.doi.org/10.1002/jgt.21832. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.





You might also like



Downloadable Citations