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

Abstrakt

We relate the existence of hamiltonian structures of interval graphs to the scattering number.

Klíčová slova

• interval graphs
• hamiltonian path
• hamiltonian cycle
• scattering number