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

DOI10.1016/J.ENDM.2011.05.038MaRDI QIDQ2840712zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmcircular-arc graphscountingdynamic programminginterval graphslongest path problem

Mathematics Subject Classification ID

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

Recommendations

• Computing and counting longest paths on circular-arc graphs in polynomial time
• A note on longest paths in circular arc graphs
• Longest Paths in Circular Arc Graphs
• Publication:4733880
• Polynomial time algorithms on circular-arc overlap graphs
• Linear time algorithms on circular-arc graphs
• Efficient reduction for path problems on circular-arc graphs
• Pathwidth of Circular-Arc Graphs
• scientific article; zbMATH DE number 140475
• On approximating the longest path in a graph

Cites work

• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Algorithms and Computation
• Finding Hamiltonian circuits in interval graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Paths in interval graphs and circular arc graphs
• Random generation of combinatorial structures from a uniform distribution
• The longest path problem has a polynomial solution on interval graphs
• The longest path problem is polynomial on cocomparability graphs

Cited in

(3)

• Computing and counting longest paths on circular-arc graphs in polynomial time
• A note on longest paths in circular arc graphs
• Efficient reduction for path problems on circular-arc 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 Q2840712)