Computing and counting longest paths on circular-arc graphs in polynomial time

DOI10.1016/J.DAM.2012.08.024MaRDI QIDQ2448873zbMATH OpenOpenAlexDBLPWikidataFDO

Authors George B. Mertzios, Ivona Bezáková

Publication date 5 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.08.024

zbMATH Keywords

dynamic programmingapproximation algorithminterval graphscircular-arc graphscountinglongest path problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Paths and cycles (05C38)

Recommendations

• Computing and counting longest paths on circular-arc graphs in polynomial time
• Paths in interval graphs and circular arc graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem has a polynomial solution on interval graphs
• The longest cycle problem is polynomial on interval graphs

Cites work

• scientific article; zbMATH DE number 1003265 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1024108 (Why is no real title available?)
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Achromatic number is NP-complete for cographs and interval graphs
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Finding a Path of Superlogarithmic Length
• Linear algorithm for optimal path cover problem on interval graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• On approximating the longest path in a graph
• On computing a longest path in a tree
• On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
• Paths in interval graphs and circular arc graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Random generation of combinatorial structures from a uniform distribution
• Self-testing algorithms for self-avoiding walks
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• The Complexity of Coloring Circular Arcs and Chords
• The longest path problem has a polynomial solution on interval graphs
• The longest path problem is polynomial on cocomparability graphs

Cited in

(10)

• The Longest Path Problem Is Polynomial on Interval Graphs
• Detour trees
• A note on longest paths in circular arc graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• A linear time algorithm for computing longest paths in cactus graphs
• Efficient reduction for path problems on circular-arc graphs
• Contracting to a longest path in H-free graphs
• An approximation algorithm for computing longest paths.
• The longest cycle problem is polynomial on interval graphs
• The Hamiltonian connectivity of rectangular supergrid graphs

This page was built for publication: Computing and counting longest paths on circular-arc graphs in polynomial time

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