Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

DOI10.1007/978-3-642-45043-3_12MaRDI QIDQ2864296zbMATHOpenAlexFDO

Authors Jiří Fiala, Petr A. Golovach, Tomáš Kaiser, Daniël Paulusma, Andrzej Proskurowski, Hajo Broersma

Publication date 6 December 2013

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/14197/1/14197.pdf

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Recommendations

• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Computing the weighted isolated scattering number of interval graphs in polynomial time
• A polynomial algorithm for weighted scattering number in interval graphs
• The scattering number of strictly chordal graphs: linear time determination
• The neighbour-scattering number can be computed in polynomial time for interval graphs
• Linear algorithm for domatic number problem on interval graphs
• Scattering number and extremal non-Hamiltonian graphs
• Computing the Scattering Number of Graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Spanning connectedness and Hamiltonian thickness of graphs and interval graphs

Cited in

(7)

• The neighbour-scattering number can be computed in polynomial time for interval graphs
• Computing the weighted isolated scattering number of interval graphs in polynomial time
• Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
• Scattering number and extremal non-Hamiltonian graphs
• A polynomial algorithm for weighted scattering number in interval graphs
• Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs

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 Q2864296)