A simple linear-time recognition algorithm for weakly quasi-threshold graphs€
Φόρτωση...
Ημερομηνία
Συγγραφείς
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Springer Verlag (Germany)
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Graphs and Combinatorics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a ?nite set of forbidden subgraphs: the class of weakly quasi- threshold graphs coincides with the class of fP4; co-(2P3)g-free graphs. Moreover we give the ?rst linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certi?cates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional O(n) time. Furthermore we give a linear-time algorithm for ?nding the largest induced weakly quasi-threshold subgraph in a cograph.
Περιγραφή
Λέξεις-κλειδιά
Weakly quasi-threshold graphs, cographs, forbidden induced subgraphs, recog-, nition, linear-time algorithms
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών