The longest cycle problem is polynomial on interval graphs

DOI10.1016/J.TCS.2021.01.005MaRDI QIDQ2227488zbMATH OpenOpenAlexFDO

Authors Jianhui Shang, Peng Li, Yi Shi

Publication date 15 February 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.01.005

zbMATH Keywords

\(k\)-thick graphsdynamic programminginterval graphslongest cycle problemlongest path problempolynomial algorithm

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem has a polynomial solution on interval graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Longest cycles in polyhedral graphs
• Computing and Combinatorics
• The longest path problem is polynomial on cocomparability graphs
• The longest path problem is polynomial on cocomparability graphs
• On the Intersections of Longest Cycles in a Graph
• scientific article; zbMATH DE number 3979098

Cites work

• A linear time algorithm for computing longest paths in 2-trees.
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A note on Hamiltonian circuits
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Algorithmic graph theory and perfect graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• An improved upper bound on the length of the longest cycle of a supercritical random graph
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Approximating the Longest Cycle Problem in Sparse Graphs
• Beautiful conjectures in graph theory
• Chords of longest cycles in cubic graphs
• Computing and Combinatorics
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Determinants and Longest Cycles of Graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian results inK1,3-free graphs
• scientific article; zbMATH DE number 3875324 (Why is no real title available?)
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 1057882 (Why is no real title available?)
• Intersections of longest cycles in \(k\)-connected graphs
• Large degree vertices in longest cycles of graphs. I
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Longest cycles in \(k\)-connected graphs with given independence number
• Longest cycles in threshold graphs
• Paths in interval graphs and circular arc graphs
• Relative length of longest paths and cycles in 2-connected graphs
• Removable edges and chords of longest cycles in 3-connected graphs
• Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
• The longest path problem has a polynomial solution on interval graphs
• The longest path problem is polynomial on cocomparability graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• The ratio of the longest cycle and longest path in semicomplete multipartite digraphs
• Transversals of Longest Paths and Cycles

Cited in

(12)

• A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
• Polynomial time algorithm for k-vertex-edge dominating problem in interval graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The Longest Path Problem Is Polynomial on Interval Graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• The longest path problem has a polynomial solution on interval graphs
• The k-th Roman domination problem is polynomial on interval graphs
• Semi-proper interval graphs
• On the unit interval graphs which are paired k-disjoint path coverable
• Finding the longest isometric cycle in a graph

This page was built for publication: The longest cycle problem is polynomial on interval graphs

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