Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time
From MaRDI portal
Publication:2840712
DOI10.1016/j.endm.2011.05.038zbMath1268.05209MaRDI QIDQ2840712
George B. Mertzios, Ivona Bezáková
Publication date: 23 July 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.038
dynamic programming; approximation algorithm; counting; interval graphs; circular-arc graphs; longest path problem
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- The longest path problem has a polynomial solution on interval graphs
- Finding Hamiltonian circuits in interval graphs
- Random generation of combinatorial structures from a uniform distribution
- Paths in interval graphs and circular arc graphs
- The Longest Path Problem is Polynomial on Cocomparability Graphs
- A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
- Algorithms and Computation