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

DOI10.1016/J.DAM.2012.08.024zbMATH Open1288.05137DBLPjournals/dam/MertziosB14OpenAlexW2172690851WikidataQ56639273 ScholiaQ56639273MaRDI QIDQ2448873FDOQ2448873

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

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

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)

Cites Work

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

Cited In (10)

• The longest cycle problem is polynomial on interval graphs
• A linear time algorithm for computing longest paths in cactus graphs
• Detour trees
• An approximation algorithm for computing longest paths.
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The Hamiltonian connectivity of rectangular supergrid graphs
• Contracting to a longest path in H-free graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• 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 Q2448873)