### Abstract

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers |

Editors | Andreas Brandstädt, Klaus Jansen, Rüdiger Reischuk |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 127-138 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-642-45043-3 |

ISBN (Print) | 978-3-642-45042-6 |

DOIs | |

Publication status | Published - 2013 |

Event | 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 - Lübeck, Germany Duration: 19 Jun 2013 → 21 Jun 2013 Conference number: 39 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 8165 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 |
---|---|

Abbreviated title | WG |

Country | Germany |

City | Lübeck |

Period | 19/06/13 → 21/06/13 |

### Fingerprint

### Keywords

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

### Cite this

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -