Broersma, H.J. and Fiala, J. and Golovach, P.A. and Kaiser, T. and Paulusma, D. and Proskurowski, A. (2013) 'Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs.', in Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers. Berlin, Heidelberg: Springer, pp. 127-138. Lecture notes in computer science. (8165).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (353Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-45043-3_12 |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-45043-3_12 |
| Date accepted: | No date available |
| Date deposited: | 15 January 2015 |
| Date of first online publication: | 2013 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
