OPTIMIZATIONACADEMIC WEBSITE
26 Mar 2019

The Steiner Cycle and Path Cover Problem on Interval Graphs

We present linear time algorithms for the Steiner path cover and Steiner cycle problems 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.

Comments Off on The Steiner Cycle and Path Cover Problem on Interval Graphs