Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Mathematics and Theoretical Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper, we consider the recognition problem on three classes of perfect graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min{m alpha(n,n), m + n log n}) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O( n min{m alpha(n, n), m + n log n})-time and O( n + m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement (G) over bar of the graph G is HH-free can be efficiently resolved in O(nm) time using O(n(2)) space, which leads to an O(nm)-time and O(n(2))-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n(3)) time and O(n(2)) space.
Περιγραφή
Λέξεις-κλειδιά
hh-free graph, hhd-free graph, welsh-powell opposition graph, perfectly orderable graph, recognition, perfectly orderable graphs, complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής