On the recognition of P-4-comparability graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Graph-Theoretic Concepts in Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We consider the problem of recognizing whether a simple undirected graph is a P-4-comparability graph. This problem has been considered by Hoang and Reed who described an O(n(4))-time algorithm for its solution, where n is the number of vertices of the given graph. Faster algorithms have recently been presented by Raschle and Simon and by Nikolopoulos and Palios; the time complexity of both algorithms is O(n + m(2)), where m is the number of edges of the graph. In this paper, we describe an O(n m)-time, O(n + m)-space algorithm for the recognition of P-4-comparability graphs. The algorithm computes the P(4)s of the input graph G by means of the BFS-trees of the complement of G rooted at each of its vertices, without however explicitly computing the complement of G. Our algorithm is simple, uses simple data structures, and leads to an O(n m)-time algorithm for computing an acyclic P-4-transitive orientation of a P-4-comparability graph.
Περιγραφή
Λέξεις-κλειδιά
perfectly orderable graph, comparability graph, p-4-comparability graph, recognition, p-4-component, p-4-transitive orientation, perfectly orderable graphs, comparability, algorithms
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής