Recognizing bipolarizable and P-4-simplicial graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό 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
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής