On the recognition of bipolarizable and P-4-simplicial graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Mathematics and Theoretical Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
The classes of Raspail ( also known as Bipolarizable) and P-4-simplicial graphs were introduced by Hoang and Reed who showed that both classes are perfectly orderable and admit polynomial-time recognition algorithms [16]. In this paper, we consider the recognition problem on these classes of graphs and present algorithms that solve it in O(nm) time. In particular, we prove properties of the graphs investigated and show that we can produce bipolarizable and P-4-simplicial orderings on the vertices of the input graph G, if such orderings exist, working only on P(3)s that participate in a P-4 of G. The proposed recognition algorithms are simple, use simple data structures and both require O(n+m) space. Additionally, we show how our recognition algorithms can be augmented to provide certificates, whenever they decide that G is not bipolarizable or P-4-simplicial; the augmentation takes O(n + m) time and space. Finally, we include a diagram on class inclusions and the currently best recognition time complexities for a number of perfectly orderable classes of graphs.
Περιγραφή
Λέξεις-κλειδιά
bipolarizable (raspail) graphs, p-4-simplicial graphs, perfectly orderable graphs, recognition, algorithms, complexity, perfectly orderable graphs, brittle graphs, linear-time, orientation, algorithms, complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής