On the recognition of P-4-comparability graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Τίτλος Εφημερίδας
Περιοδικό 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
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής