Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11017Full metadata record
| DC Field | Value | Language |
|---|---|---|
| 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.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2009 | - |
| 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.journalName | Ars Combinatoria | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nikolopoulos-2009-Counting Spanning Trees in Cographs An Algorithmic Approach.pdf | 244.95 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
