The Steiner cycle and path cover problem on interval graphs

DOI10.1007/S10878-021-00757-7MaRDI QIDQ2075469zbMATH OpenOpenAlexFDO

Authors Ante Ćustić, Stefan Lendl

Publication date 14 February 2022

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• Exact solutions for the Steiner path cover problem on special graph classes
• Computing directed Steiner path covers
• Paths in interval graphs and circular arc graphs
• On the \(k\)-path cover problem for cacti
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs

Cites work

• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Approximability of the minimum Steiner cycle problem
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• Deferred-query: An efficient approach for some problems on interval graphs
• Exact solutions for the Steiner path cover problem on special graph classes
• Finding Hamiltonian circuits in interval graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• The Steiner cycle polytope

Cited in

(5)

• Exact solutions for the Steiner path cover problem on special graph classes
• Computing directed Steiner path covers
• scientific article; zbMATH DE number 5977185 (Why is no real title available?)
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• A branch-and-cut algorithm for the multiple Steiner TSP with order constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2075469)