Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

Haitze J. Broersma, Jiri Fiala, Petr A. Golovach, Tomas Kaiser, Daniël Paulusma, Andrzej Proskurowski

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
4 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers
EditorsAndreas Brandstädt, Klaus Jansen, Rüdiger Reischuk
Place of PublicationBerlin
PublisherSpringer
Pages127-138
Number of pages12
ISBN (Electronic)978-3-642-45043-3
ISBN (Print)978-3-642-45042-6
DOIs
Publication statusPublished - 2013
Event39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 - Lübeck, Germany
Duration: 19 Jun 201321 Jun 2013
Conference number: 39

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8165
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013
Abbreviated titleWG
CountryGermany
CityLübeck
Period19/06/1321/06/13

Fingerprint

Interval Graphs
Linear-time Algorithm
Connectivity
Scattering
If and only if
Computing

Keywords

  • MSC-05C
  • EWI-24425
  • IR-89270
  • METIS-302692
  • Hamilton-connectivity
  • Linear algorithm
  • Scattering number
  • Interval graph

Cite this

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, Lübeck, Germany, June 19-21, 2013, Revised Papers (pp. 127-138). (Lecture Notes in Computer Science; Vol. 8165). Berlin: Springer. https://doi.org/10.1007/978-3-642-45043-3_12
Broersma, Haitze J. ; Fiala, Jiri ; Golovach, Petr A. ; Kaiser, Tomas ; Paulusma, Daniël ; Proskurowski, Andrzej. / Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. editor / Andreas Brandstädt ; Klaus Jansen ; Rüdiger Reischuk. Berlin : Springer, 2013. pp. 127-138 (Lecture Notes in Computer Science).
@inproceedings{97852a947a3043e88b3e81134ef5be81,
title = "Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs",
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{\"u}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.",
keywords = "MSC-05C, EWI-24425, IR-89270, METIS-302692, Hamilton-connectivity, Linear algorithm, Scattering number, Interval graph",
author = "Broersma, {Haitze J.} and Jiri Fiala and Golovach, {Petr A.} and Tomas Kaiser and Dani{\"e}l Paulusma and Andrzej Proskurowski",
note = "10.1007/978-3-642-45043-3_12",
year = "2013",
doi = "10.1007/978-3-642-45043-3_12",
language = "English",
isbn = "978-3-642-45042-6",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "127--138",
editor = "Andreas Brandst{\"a}dt and Klaus Jansen and R{\"u}diger Reischuk",
booktitle = "Graph-Theoretic Concepts in Computer Science",

}

Broersma, HJ, Fiala, J, Golovach, PA, 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, Lübeck, Germany, June 19-21, 2013, Revised Papers. Lecture Notes in Computer Science, vol. 8165, Springer, Berlin, pp. 127-138, 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, Lübeck, Germany, 19/06/13. https://doi.org/10.1007/978-3-642-45043-3_12

Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. / Broersma, Haitze J.; Fiala, Jiri; Golovach, Petr A.; Kaiser, Tomas; Paulusma, Daniël; Proskurowski, Andrzej.

Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. ed. / Andreas Brandstädt; Klaus Jansen; Rüdiger Reischuk. Berlin : Springer, 2013. p. 127-138 (Lecture Notes in Computer Science; Vol. 8165).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

AU - Broersma, Haitze J.

AU - Fiala, Jiri

AU - Golovach, Petr A.

AU - Kaiser, Tomas

AU - Paulusma, Daniël

AU - Proskurowski, Andrzej

N1 - 10.1007/978-3-642-45043-3_12

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - MSC-05C

KW - EWI-24425

KW - IR-89270

KW - METIS-302692

KW - Hamilton-connectivity

KW - Linear algorithm

KW - Scattering number

KW - Interval graph

U2 - 10.1007/978-3-642-45043-3_12

DO - 10.1007/978-3-642-45043-3_12

M3 - Conference contribution

SN - 978-3-642-45042-6

T3 - Lecture Notes in Computer Science

SP - 127

EP - 138

BT - Graph-Theoretic Concepts in Computer Science

A2 - Brandstädt, Andreas

A2 - Jansen, Klaus

A2 - Reischuk, Rüdiger

PB - Springer

CY - Berlin

ER -

Broersma HJ, Fiala J, Golovach PA, Kaiser T, Paulusma D, Proskurowski A. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. In Brandstädt A, Jansen K, Reischuk R, editors, Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. Berlin: Springer. 2013. p. 127-138. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-45043-3_12