Given two matroids and on a common ground set with base sets and , some integer , and two cost functions , we consider the optimization problem to find a basis and a basis minimizing cost subject to either a lower bound constraint , an upper bound constraint , or an equality constraint on the […]

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.