Open Access
Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial
-
Full Text Views
98
- Cite this
- Free PDF (775.5KB)
Summary :
Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1022-1027
- Publication Date
- 2019/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.1022
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Graph algorithms
Authors
Farley Soares OLIVEIRA
The University of Tokyo
Hidefumi HIRAISHI
The University of Tokyo
Hiroshi IMAI
The University of Tokyo
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Farley Soares OLIVEIRA, Hidefumi HIRAISHI, Hiroshi IMAI, "Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1022-1027, September 2019, doi: 10.1587/transfun.E102.A.1022.
Abstract: Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1022/_p
Copy
@ARTICLE{e102-a_9_1022,
author={Farley Soares OLIVEIRA, Hidefumi HIRAISHI, Hiroshi IMAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial},
year={2019},
volume={E102-A},
number={9},
pages={1022-1027},
abstract={Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).},
keywords={},
doi={10.1587/transfun.E102.A.1022},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1022
EP - 1027
AU - Farley Soares OLIVEIRA
AU - Hidefumi HIRAISHI
AU - Hiroshi IMAI
PY - 2019
DO - 10.1587/transfun.E102.A.1022
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).
ER -
English
