Recognizing bipolarizable and P-4-simplicial graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Graph-Theoretic Concepts in Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Hoang and Reed defined the classes of Raspail (also known as Bipolarizable) and P-4-simplicial graphs, both of which are perfectly orderable, and proved that they 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, where n and m are the numbers of vertices and of edges of the input graph. In particular, we prove properties and show that we can produce bipolarizable and P-4-simplicial orderings on the vertices of a graph G, if such orderings exist, working only on P(3)s that participate in P(4)s of G. The proposed recognition algorithms are simple, use simple data structures and require O(n + m) space. Moreover, we present a diagram on class inclusions and the currently best recognition time complexities for a number of perfectly orderable classes of graphs and some preliminary results on forbidden subgraphs for the class of P-4-simplicial graphs.
Περιγραφή
Λέξεις-κλειδιά
bipolarizable (raspail) graph, p-4-simplicial graph, perfectly orderable graph, recognition, algorithm, complexity, forbidden subgraph, perfectly orderable graphs, recognition algorithm, brittle graphs, linear-time, complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής