Algorithms for P-4-comparability graph recognition and acyclic P-4-transitive orientation
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Algorithmica
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We consider two problems pertaining to P-4-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P-4-comparability graph and the problem of producing an acyclic P-4-transitive orientation of a P-4-comparability graph. These problems have been considered by HoAng and Reed who described o(n(4))- and o(n(5))-time algorithms for their solution, respectively, where n is the number of vertices of the input graph. Faster algorithms have recently been presented by Raschle and Simon, and by Nikolopoulos and Palios; the time complexity of these algorithms for either problem is o (n + m(2)), where m is the number of edges of the graph. In this paper we describe O (nm)-time and O (n + m)-space algorithms for the recognition and the acyclic P-4-transitive orientation problems on P-4-comparability graphs. The algorithms rely on properties of the P-4-components of a graph, which we establish, and on the efficient construction of the P4-components by means of the BFS-trees of the complement of the graph rooted at each of its vertices, without however explicitly computing the complement. Both algorithms are simple and use simple data structures.
Περιγραφή
Λέξεις-κλειδιά
perfectly orderable graph, comparability graph, p-4-comparability graph, p-4-component, recognition, p-4-transitive orientation, perfectly orderable graphs, comparability-graphs, efficient
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής