Pseudo-hamiltonian graphs

A pseudo-h-hamiltonian cycle in a graph is a closed walk that visits every vertex exactly h times. We present a variety of combinatorial and algorithmic results on pseudo-h-hamiltonian cycles. First, we show that deciding whether a graph is pseudo-h-hamiltonian is NP-complete for any given h > 1....

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Babel Luitpold
Woeginger Gerhard J.
Dokumentumtípus: Cikk
Megjelent: 2000
Sorozat:Acta cybernetica 14 No. 4
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12649
Leíró adatok
Tartalmi kivonat:A pseudo-h-hamiltonian cycle in a graph is a closed walk that visits every vertex exactly h times. We present a variety of combinatorial and algorithmic results on pseudo-h-hamiltonian cycles. First, we show that deciding whether a graph is pseudo-h-hamiltonian is NP-complete for any given h > 1. Surprisingly, deciding whether there exists an h > 1 such that the graph is pseudo-h-hamiltonian, can be done in polynomial time. We also present sufficient conditions for pseudo-h-hamiltonicity that axe based on stable sets and on toughness. Moreover, we investigate the computational complexity of finding pseudo-h-hamiltonian cycles on special graph classes like bipartite graphs, split graphs, planar graphs, cocomparability graphs; in doing this, we establish a precise separating line between easy and difficult cases of this problem.
Terjedelem/Fizikai jellemzők:553-567
ISSN:0324-721X