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, 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 |
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
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Matching cuts in graphs of high girth and H-free graphs
(2023)
Presentation / Conference Contribution
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Presentation / Conference Contribution
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