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

Keywords

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

Fingerprint Dive into the research topics of 'Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs'. Together they form a unique fingerprint.

  • 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