Recognition and orientation algorithms for P-4-comparability graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Algorithms and Computation, Proceedings
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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 given graph. Recently, Raschle and Simon described O(n + m(2))-time algorithms for these problems, where m is the number of edges of the graph. In this paper, we describe different O(n + m(2))-time algorithms for the recognition and the acyclic P-4-transitive orientation problems on P-4-comparability graphs. Instrumental in these algorithms are structural relationships of the P-4-components of a graph, which we establish and which are interesting in their own right. Our algorithms are simple, use simple data structures, and have the advantage over those of Raschle and Simon in that they are non-recursive, require linear space and admit efficient parallelization.
Περιγραφή
Λέξεις-κλειδιά
comparability
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής