The longest cycle problem is polynomial on interval graphs

DOI10.1016/j.tcs.2021.01.005zbMath1502.68247OpenAlexW3120803488MaRDI QIDQ2227488

Jianhui Shang, Yi Shi, Peng Li

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 programmingpolynomial algorithminterval graphslongest path problemlongest cycle problem\(k\)-thick graphs

Mathematics Subject Classification ID

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

Related Items (3)

Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs ⋮ Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Large degree vertices in longest cycles of graphs. I
• The longest path problem has a polynomial solution on interval graphs
• Longest cycles in \(k\)-connected graphs with given independence number
• 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
• Paths in interval graphs and circular arc graphs
• Longest cycles in threshold graphs
• Intersections of longest cycles in \(k\)-connected graphs
• Chords of longest cycles in cubic graphs
• Algorithmic graph theory and perfect graphs
• The longest path problem is polynomial on cocomparability graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• Removable edges and chords of longest cycles in 3-connected graphs
• Beautiful conjectures in graph theory
• Computing and counting longest paths on circular-arc graphs in polynomial time
• A note on Hamiltonian circuits
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Approximating the Longest Cycle Problem in Sparse Graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• Hamiltonian results inK1,3-free graphs
• Determinants and Longest Cycles of Graphs
• Relative Length of Longest Paths and Cycles in 2-Connected Graphs
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
• Transversals of Longest Paths and Cycles
• An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph
• Computing and Combinatorics
• The ratio of the longest cycle and longest path in semicomplete multipartite digraphs

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