Detecting holes and antiholes in graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Algorithmica
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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 + m(2)) 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(n(4))-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 P-4 (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(n(k-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 + m(2)) time requiring O(n + m) space. Again, for a fixed constant k >= 6, the approach can be extended to yield O(n(k-2))-time and O(n(2))-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.
Περιγραφή
Λέξεις-κλειδιά
holes, antiholes, weakly chordal graphs, co-connectivity, weakly triangulated graphs, linear-time algorithms, recognition
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής