Computing and counting longest paths on circular-arc graphs in polynomial time
From MaRDI portal
Publication:2448873
DOI10.1016/j.dam.2012.08.024zbMath1288.05137WikidataQ56639273 ScholiaQ56639273MaRDI QIDQ2448873
Ivona Bezáková, George B. Mertzios
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
dynamic programming; approximation algorithm; counting; interval graphs; circular-arc graphs; longest path problem
05C35: Extremal problems in graph theory
90C39: Dynamic programming
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Contracting to a longest path in H-free graphs, Detour trees, The Hamiltonian connectivity of rectangular supergrid graphs, The longest cycle problem is polynomial on interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The longest path problem has a polynomial solution on interval graphs
- On approximating the longest path in a graph
- Linear algorithm for optimal path cover problem on interval graphs
- Finding Hamiltonian circuits in proper interval graphs
- Finding Hamiltonian circuits in interval graphs
- Random generation of combinatorial structures from a uniform distribution
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Paths in interval graphs and circular arc graphs
- On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
- On computing a longest path in a tree
- Achromatic number is NP-complete for cographs and interval graphs
- Algorithmic graph theory and perfect graphs
- Linear structure of bipartite permutation graphs and the longest path problem
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Self-testing algorithms for self-avoiding walks
- The Longest Path Problem is Polynomial on Cocomparability Graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Finding a Path of Superlogarithmic Length
- A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
- Algorithms and Computation
