Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
From MaRDI portal
Publication:5265335
Abstract: Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval graph has a Hamilton cycle if and only if its scattering number is at most 0. We complete this characterization by proving that for all k<=-1 an interval graph is -(k+1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(m+n) time algorithm for computing the scattering number of an interval graph with n vertices an m edges, which improves the O(n^4) time bound of Kratsch, Kloks and M"uller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(m+n) time.
Recommendations
- Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
- A polynomial algorithm for weighted scattering number in interval graphs
- Computing the weighted isolated scattering number of interval graphs in polynomial time
- The neighbour-scattering number can be computed in polynomial time for interval graphs
- Finding Hamiltonian circuits in interval graphs
Cites work
- 1-tough cocomparability graphs are hamiltonian
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Deferred-query: An efficient approach for some problems on interval graphs
- 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 617594 (Why is no real title available?)
- scientific article; zbMATH DE number 1124477 (Why is no real title available?)
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Linear algorithm for optimal path cover problem on interval graphs
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Measuring the vulnerability for classes of intersection graphs
- On a class of posets and the corresponding comparability graphs
- On spanning disjoint paths in line graphs
- On the spanning connectivity of graphs
- Paths in interval graphs and circular arc graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Powers of Hamiltonian paths in interval graphs
- Proper interval graphs and the guard problem
- Recognizing tough graphs is NP-hard
- Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- The longest path problem has a polynomial solution on interval graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
- Tough graphs and Hamiltonian circuits.
Cited in
(18)- The neighbour-scattering number can be computed in polynomial time for interval graphs
- Long paths and toughness of \(k\)-trees and chordal planar graphs
- The scattering number of strictly chordal graphs: linear time determination
- Characterization of interval graphs that are unpaired 2-disjoint path coverable
- Computing the weighted isolated scattering number of interval graphs in polynomial time
- Disjoint path covers joining prescribed source and sink sets in interval graphs
- A polynomial algorithm for weighted scattering number in interval graphs
- Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
- Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
- A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
- The vertex attack tolerance of complex networks
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Semi-proper interval graphs
- Vertex vulnerability in wrapped butterfly network
- Isolated scattering number can be computed in polynomial time for interval graphs
- A polynomial kernel for deletion to the scattered class of cliques and trees
- A polynomial kernel for deletion to the scattered class of cliques and trees
- Cyclability in graph classes
This page was built for publication: Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265335)
