Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time

DOI10.1016/j.endm.2011.05.038zbMath1268.05209OpenAlexW2118294657MaRDI 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

zbMATH Keywords

dynamic programmingapproximation algorithmcountinginterval graphscircular-arc graphslongest path problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

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

This page was built for publication: Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time