The longest cycle problem is polynomial on interval graphs

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

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

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

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)

Cites Work

• Algorithmic graph theory and perfect graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• 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
• The Longest Path Problem Is Polynomial on Interval Graphs
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
• Linear algorithm for optimal path cover problem on interval graphs
• A note on Hamiltonian circuits
• Large degree vertices in longest cycles of graphs. I
• Longest cycles in \(k\)-connected graphs with given independence number
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Hamiltonian results inK1,3-free graphs
• Transversals of Longest Paths and Cycles
• Computing and Combinatorics
• Finding Hamiltonian circuits in interval graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths in interval graphs and circular arc graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• Approximating the Longest Cycle Problem in Sparse Graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• The longest path problem has a polynomial solution on interval graphs
• Determinants and Longest Cycles of Graphs
• Chords of longest cycles in cubic graphs
• Removable edges and chords of longest cycles in 3-connected graphs
• Beautiful conjectures in graph theory
• The longest path problem is polynomial on cocomparability graphs
• Intersections of longest cycles in \(k\)-connected graphs
• Title not available (Why is that?)
• Longest cycles in threshold graphs
• The ratio of the longest cycle and longest path in semicomplete multipartite digraphs
• Relative Length of Longest Paths and Cycles in 2-Connected Graphs
• An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph
• Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
• Title not available (Why is that?)

Cited In (5)

• 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 \(k\)-th Roman domination problem is polynomial on interval graphs
• Semi-proper 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)