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....
Elmentve itt :
| Szerzők: | |
|---|---|
| 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 |
| LEADER | 01622nab a2200241 i 4500 | ||
|---|---|---|---|
| 001 | acta12649 | ||
| 005 | 20220614102304.0 | ||
| 008 | 161015s2000 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Babel Luitpold | |
| 245 | 1 | 0 | |a Pseudo-hamiltonian graphs |h [elektronikus dokumentum] / |c Babel Luitpold |
| 260 | |c 2000 | ||
| 300 | |a 553-567 | ||
| 490 | 0 | |a Acta cybernetica |v 14 No. 4 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Matematika | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 700 | 0 | 1 | |a Woeginger Gerhard J. |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12649/1/cybernetica_014_numb_004_553-567.pdf |z Dokumentum-elérés |