ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
From MaRDI portal
Publication:3065608
DOI10.1142/S0129054107005054zbMATH Open1202.68291OpenAlexW2058687965MaRDI QIDQ3065608FDOQ3065608
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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Finding Hamiltonian circuits in proper interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On computing a longest path in a tree
- Algorithmic graph theory and perfect graphs
- Color-coding
- Finding a Path of Superlogarithmic Length
- On approximating the longest path in a graph
- Bipartite permutation graphs
- HAMILTONian circuits in chordal bipartite graphs
- Node-Deletion Problems on Bipartite Graphs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Bandwidth of chain graphs
- Bipartite permutation graphs with application to the minimum buffer size problem
- Finding Hamiltonian circuits in interval graphs
- Hamiltonian circuits in interval graph generalizations
- The Hamiltonian circuit problem for circle graphs is NP-complete
- Recognizing interval digraphs and interval bigraphs in polynomial time
- A linear time recognition algorithm for proper interval graphs
- A note on Hamiltonian split graphs
- Paths in interval graphs and circular arc graphs
- An approximation algorithm for computing longest paths.
- Necessary conditions for Hamiltonian split graphs
- Longest cycles in threshold graphs
Cited In (23)
- A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs
- An approximation algorithm for the longest cycle problem in solid grid graphs
- Reconstruction of Interval Graphs
- On approximating the longest path in a graph
- A linear-time algorithm for the longest path problem in rectangular grid graphs
- The Hamiltonian connectivity of rectangular supergrid graphs
- Longest (s, t)-paths in L-shaped grid graphs
- Tractabilities and intractabilities on geometric intersection graphs
- On approximating the longest path in a graph
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- Reconstruction of interval graphs
- A genetic algorithm for the picture maze generation problem
- Route-enabling graph orientation problems
- The longest path problem in odd-sized \(O\)-shaped grid graphs
- Reconfiguration of colorable sets in classes of perfect graphs
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
- A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler
- Reconfiguration of cliques in a graph
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- An approximation algorithm for the longest path problem in solid grid graphs
- Finding a shortest non-zero path in group-labeled graphs via permanent computation
- Core and Conditional Core Path of Specified Length in Special Classes of 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)
