The Steiner cycle and path cover problem on interval graphs

DOI10.1007/s10878-021-00757-7zbMath1485.90107OpenAlexW3143897082MaRDI QIDQ2075469

Stefan Lendl, Ante Ćustić

Publication date: 14 February 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00757-7

zbMATH Keywords

Hamiltonian cycleinterval graphslinear timeSteiner cycle

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (1)

Computing directed Steiner path covers

Cites Work

• Unnamed Item
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Linear algorithm for optimal path cover problem on interval graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Finding Hamiltonian circuits in interval graphs
• The Steiner cycle polytope
• Exact solutions for the Steiner path cover problem on special graph classes
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)
• Deferred-query: An efficient approach for some problems on interval graphs

This page was built for publication: The Steiner cycle and path cover problem on interval graphs