Finding a hamilton path through a family of intervals

Abstract

We develop an o(nx(n)) algorithm for computing a hamilton path in a family of n intervals, where x is an inverse of Ackerman's function. Our approach is based on a new characterization of interval graphs containing hamilton paths, related to the clique decomposition of the graph.

Keywords:

• Interval graphs
• interval families
• hamilton paths

C.R Categories:

• F.2.2 (analysis of algorithms and problem complexity)
• G.2.2 (discrete mathematics)