The longest cycle problem is polynomial on interval graphs

DOI10.1016/J.TCS.2021.01.005zbMATH Open1502.68247OpenAlexW3120803488MaRDI QIDQ2227488FDOQ2227488

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

dynamic programminginterval graphspolynomial algorithmlongest path problemlongest cycle problem\(k\)-thick graphs

Mathematics Subject Classification ID

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) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62)

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

• 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?)
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A linear time algorithm for computing longest paths in 2-trees.
• 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
• Intersections of longest cycles in \(k\)-connected graphs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Large degree vertices in longest cycles of graphs. I
• 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 Is Polynomial on Interval Graphs
• The longest path problem has a polynomial solution on interval graphs
• The longest path problem is polynomial on cocomparability graphs
• The ratio of the longest cycle and longest path in semicomplete multipartite digraphs
• Transversals of Longest Paths and Cycles

Cited In (11)

• 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 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
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The Longest Path Problem Is Polynomial on Interval Graphs
• Finding the longest isometric cycle in a graph
• 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

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)