Detecting Holes and Antiholes in Graphs |
| |
Authors: | Stavros D Nikolopoulos Leonidas Palios |
| |
Affiliation: | (1) Department of Computer Science, University of Ioannina, P.O. Box 1186, GR-45110, Ioannina, Greece |
| |
Abstract: | In this paper we study the problems of detecting holes and antiholes in general undirected graphs, and we present algorithms
for these problems. For an input graph G on n vertices and m edges, our algorithms run in O(n + m2) time and require O(n m) space; we thus provide a solution to the open problem posed by Hayward et al. asking for an O(n4)-time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is the use of the depth-first-search
traversal on appropriate auxiliary graphs in which moving between any two adjacent vertices is equivalent to walking along
a P4 (i.e., a chordless path on four vertices) of the input graph or on its complement, respectively. The approach can be generalized
so that for a fixed constant k ≥ 5 we obtain an O(nk-1)-time algorithm for the detection of a hole (antihole resp.) on at least k vertices.
Additionally, we describe a different approach which allows us to detect antiholes in graphs that do not contain chordless
cycles on five vertices in O(n + m2) time requiring O(n + m) space.
Again, for a fixed constant k ≥ 6, the approach can be extended to yield O(nk-2)-time and O(n2)-space algorithms for detecting holes (antiholes resp.) on at least k vertices in graphs which do not contain holes (antiholes
resp.) on k - 1 vertices. Our algorithms are simple and can be easily used in practice. Finally, we also show how our detection
algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph;
the augmentation takes O(n + m) time and space. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|