Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
From MaRDI portal
Publication:5265335
DOI10.1002/jgt.21832zbMath1316.05080arXiv1301.5953OpenAlexW2133847446MaRDI QIDQ5265335
Petr A. Golovach, Andrzej Proskurowski, Daniël Paulusma, Jiří Fiala, Tomáš Kaiser, Hajo J. Broersma
Publication date: 23 July 2015
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1301.5953
Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)
Related Items (10)
Long paths and toughness of \(k\)-trees and chordal planar graphs ⋮ Cyclability in graph classes ⋮ The scattering number of strictly chordal graphs: linear time determination ⋮ Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ The vertex attack tolerance of complex networks ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ A polynomial algorithm for weighted scattering number in interval graphs ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Computing the weighted isolated scattering number of interval graphs in polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- The longest path problem has a polynomial solution on interval graphs
- On the spanning connectivity of graphs
- Linear algorithm for optimal path cover problem on interval graphs
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Recognizing tough graphs is NP-hard
- Finding Hamiltonian circuits in proper interval graphs
- Finding Hamiltonian circuits in interval graphs
- Hamiltonian circuits in interval graph generalizations
- Paths in interval graphs and circular arc graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On a class of posets and the corresponding comparability graphs
- 1-tough cocomparability graphs are hamiltonian
- Proper interval graphs and the guard problem
- Measuring the vulnerability for classes of intersection graphs
- HAMILTONian circuits in chordal bipartite graphs
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- Tough graphs and Hamiltonian circuits.
- On spanning disjoint paths in line graphs
- LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
- Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Powers of Hamiltonian paths in interval graphs
- Graph Classes: A Survey
- Deferred-query: An efficient approach for some problems on interval graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
This page was built for publication: Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
