Computing the Toughness and the Scattering Number for Interval and Other Graphs
Dieter Kratsch, T. Klots, Haiko Müller, 35 - Rennes (France). Inst. de Recherche en Informatique et Systemes Aleatoires (IRISA) Centre National de la Recherche Scientifique (CNRS), 35 (France). Inst. de Recherche en Informatique et Systemes Aleatoires (IRISA) Rennes-1 Univ., 35 (France). Inst . de Recherche en Informatique et Systemes Aleatoires (IRISA) Institut National des Sciences Appliquees de Rennes (INSA), 35 (France). Unite de Recherche de Rennes Institut National de Recherche en Informatique et en Automatique (INRIA) · 1994
: We show that the scattering number and the toughness of a graph, two graph parameters strongly related to hamiltonian properties of graphs, can be computed in polynomial time on interval graphs, circular-arc graphs, permutation graphs, circular permutation graphs, trapezoid graphs and cocomparability graphs of bounded dimension. This leads to new algorithms deciding whether a graph has a hamiltonian circuit and a hamiltonian path, respectively, for some of these classes. (R'esum'e : tsvp) IRISA, Campus de Beaulieu, 35042 Rennes, France. Department of Mathematics and Computing Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands. Fakultat fur Mathematik und Informatik, Friedrich-Schiller-Universitat, 07740 Jena, Germany. Centre National de la Recherche Scientifique Institut National de Recherche en Informatique (URA 227) Universit e de Rennes 1 -- Insa de Rennes et en Automatique -- unit e de recherche de Rennes Calcul du nombre de coriacit'e et de...