H. J. Broersma
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
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 |
Files
Accepted Conference Proceeding
(361 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-45043-3_12
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search