## Abstract

The Steiner path problem is a common generalization of the Steiner tree and the Hamiltonian path problem, in which we have to decide if for a given graph there exists a path visiting a fixed set of terminals. In the Steiner cycle problem we look for a cycle visiting all terminals instead of a path. The Steiner path cover problem is an optimization variant of the Steiner path problem generalizing the path cover problem, in which one has to cover all terminals with a minimum number of paths. We study those problems for the special class of interval graphs. We present linear time algorithms for both the Steiner path cover problem and the Steiner cycle problem on interval graphs given as endpoint sorted lists. The main contribution is a lemma showing that backward steps to non-Steiner intervals are never necessary. Furthermore, we show how to integrate this modification to the deferred-query technique of Chang et al. to obtain the linear running times.

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

Pages (from-to) | 226-234 |

Number of pages | 9 |

Journal | Journal of Combinatorial Optimization |

Volume | 43 |

Issue number | 1 |

Early online date | 27 May 2021 |

DOIs | |

Publication status | Published - Jan 2022 |

## Keywords

- Hamiltonian cycle
- Interval graphs
- Linear time
- Steiner cycle

## ASJC Scopus subject areas

- Control and Optimization
- Applied Mathematics
- Discrete Mathematics and Combinatorics
- Computer Science Applications
- Computational Theory and Mathematics