Name
Abstract | ||
|---|---|---|
A cycle cover of a graph G is a collection of disjoint cycles that spans G. Generally, a (possibly discon- nected) cycle cover is easier to construct than a con- nected (Hamiltonian) cycle cover. One might expect this since the cycle cover property is local whereas connectivity is a global constraint. We compare the hardness of CONNECTED CYCLE COVER and CY- CLE COVER under various constraints (both local and global) on the orientation, crossings, and turning an- gles of edges. Surprisingly perhaps, under specific con- straints, the cycle cover problem is NP-hard whereas the corresponding connected cycle cover problem can be solved in polynomial time. |
Year | Venue | Keywords |
|---|---|---|
2002 | CCCG | polynomial time,hamiltonian cycle |
Field | DocType | Citations |
Discrete mathematics,Combinatorics,Cycle cover,Edge cover,Hamiltonian path problem,Mathematics | Conference | 1 |
PageRank | References | Authors |
0.38 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephane Durocher | 1 | 342 | 42.89 |
| David G. Kirkpatrick | 2 | 2394 | 541.05 |