The Steiner cycle and path cover problem on interval graphs

DOI10.1007/S10878-021-00757-7zbMATH Open1485.90107OpenAlexW3143897082MaRDI QIDQ2075469FDOQ2075469

Authors: Ante Ćustić, Stefan Lendl 

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

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

zbMATH Keywords

Hamiltonian cycleinterval graphslinear timeSteiner cycle

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Linear algorithm for optimal path cover problem on interval graphs
• Abusing the Tutte matrix: an algebraic instance compression for the \(K\)-set-cycle problem
• Finding Hamiltonian circuits in interval graphs
• The Steiner cycle polytope
• Approximability of the minimum Steiner cycle problem
• Deferred-query: An efficient approach for some problems on interval graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems 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
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• Exact solutions for the Steiner path cover problem on special graph classes

Cited In (4)

• Computing directed Steiner path covers
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• Exact solutions for the Steiner path cover problem on special graph classes
• Title not available (Why is that?)

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)