On computing longest paths in small graph classes

DOI10.1142/S0129054107005054MaRDI QIDQ3065608zbMATH OpenOpenAlexFDO

Authors Ryuhei Uehara, Yushi Uno

Publication date 6 January 2011

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054107005054

zbMATH Keywords

algorithmic graph theorydesign and analysis of algorithmsgraph classeslongest path problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms and Computation
• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem is polynomial on cocomparability graphs
• The longest path problem is polynomial on cocomparability graphs
• The longest path problem has a polynomial solution on interval graphs

Cites work

• A linear time recognition algorithm for proper interval graphs
• A note on Hamiltonian split graphs
• Algorithmic graph theory and perfect graphs
• An approximation algorithm for computing longest paths.
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Approximation algorithms for NP-hard problems.
• Bandwidth of chain graphs
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Color-coding
• Finding a Path of Superlogarithmic Length
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Graph Classes: A Survey
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Longest cycles in threshold graphs
• Necessary conditions for Hamiltonian split graphs
• Node-Deletion Problems on Bipartite Graphs
• On approximating the longest path in a graph
• On computing a longest path in a tree
• Paths in interval graphs and circular arc graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Hamiltonian circuit problem for circle graphs is NP-complete

Cited in

(27)

• Tractabilities and intractabilities on geometric intersection graphs
• The Hamiltonian connectivity of rectangular supergrid graphs
• Route-enabling graph orientation problems
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• A genetic algorithm for the picture maze generation problem
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Reconfiguration of colorable sets in classes of perfect graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Reconfiguration of cliques in a graph
• An approximation algorithm for the longest path problem in solid grid graphs
• A linear time algorithm for computing longest paths in 2-trees.
• A polynomial time algorithm for longest paths in biconvex graphs
• Programming and testing a two-tree algorithm
• Core and Conditional Core Path of Specified Length in Special Classes of Graphs
• A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler
• Exact and approximate algorithms for the longest induced path problem
• On approximating the longest path in a graph
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Finding a shortest non-zero path in group-labeled graphs via permanent computation
• Reconstruction of Interval Graphs
• Longest (s, t)-paths in L-shaped grid graphs
• A linear time algorithm for computing longest paths in cactus graphs
• Reconstruction of interval graphs
• The longest path problem in odd-sized O-shaped grid graphs
• On approximating the longest path in a graph
• A linear-time algorithm for the longest path problem in rectangular grid graphs

This page was built for publication: On computing longest paths in small graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3065608)