Counting Spanning Trees in Cographs: An Algorithmic Approach
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Ars Combinatoria
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper we present a new simple linear-time algorithm for determining the number of spanning trees in the class of complement reducible graphs, also known as cographs; for a cograph G on n vertices and m edges, our algorithm computes the number of spanning trees, of G in O(n + m) time and space, where the complexity of arithmetic operations is measured under the uniform cost criterion. The algorithm takes advantage of the cotree of the input cograph G and works by contracting it in a bottom-up fashion until it becomes a single node; then, the number of spanning trees of G is computed as the product of a collection of values which are associated with the vertices of G and are updated during the contraction process. The correctness of our algorithm is established through the Kirchhoff matrix tree theorem, and also relies on structural and algorithmic properties of the class of cographs. We also extend our results to a proper superclass of cographs, namely the P(4)-reducible graphs. and show that the problem of finding the number of spanning trees of a P(4)-reducible graph has linear-time solution.
Περιγραφή
Λέξεις-κλειδιά
cographs, p(4)-reducible graphs, number of spanning trees, modular decomposition, combinatorial problems, algorithms, complexity, recognition algorithm, threshold graphs, number, circulant
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής