An algorithm for computing simple k-factors |
| |
Authors: | Henk Meijer David Rappaport |
| |
Affiliation: | a Roosevelt Academy, NL-4330 AB Middelburg, The Netherlands b School of Computing, Queen's University, Kingston, ON, Canada, K7L 3N6 |
| |
Abstract: | A k-factor of graph G is defined as a k-regular spanning subgraph of G. For instance, a 2-factor of G is a set of cycles that span G. 2-factors have multiple applications in Graph Theory, Computer Graphics, and Computational Geometry. We define a simple 2-factor as a 2-factor without degenerate cycles. In general, simple k-factors are defined as k-regular spanning subgraphs where no edge is used more than once. We propose a new algorithm for computing simple k-factors for all values of k?2. |
| |
Keywords: | Graph algorithms Graph factors k-factors Simple k-factors 2-factors |
本文献已被 ScienceDirect 等数据库收录! |
|