ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES

DOI10.1142/S0129054107005054zbMath1202.68291OpenAlexW2058687965MaRDI QIDQ3065608

Yushi Uno, Ryuhei Uehara

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 theorygraph classesdesign and analysis of algorithmslongest path problem

Mathematics Subject Classification ID

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

Related Items

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Reconstruction of Interval Graphs ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Reconstruction of interval graphs ⋮ Route-enabling graph orientation problems ⋮ Reconfiguration of cliques in a graph ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Core and Conditional Core Path of Specified Length in Special Classes of Graphs ⋮ A genetic algorithm for the picture maze generation problem ⋮ A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ A linear-time algorithm for the longest path problem in rectangular grid graphs ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs

Cites Work

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