Counting Spanning Trees in Cographs: An Algorithmic Approach
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.contributor.author | Papadopoulos, C. | en |
| dc.date.accessioned | 2015-11-24T17:02:08Z | |
| dc.date.available | 2015-11-24T17:02:08Z | |
| dc.identifier.issn | 0381-7032 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11017 | |
| dc.rights | Default Licence | - |
| dc.subject | cographs | en |
| dc.subject | p(4)-reducible graphs | en |
| dc.subject | number of spanning trees | en |
| dc.subject | modular decomposition | en |
| dc.subject | combinatorial problems | en |
| dc.subject | algorithms | en |
| dc.subject | complexity | en |
| dc.subject | recognition algorithm | en |
| dc.subject | threshold graphs | en |
| dc.subject | number | en |
| dc.subject | circulant | en |
| dc.title | Counting Spanning Trees in Cographs: An Algorithmic Approach | en |
| heal.abstract | 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. | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.journalName | Ars Combinatoria | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2009 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: