Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial

• OLIVEIRA Farley Soares

  Graduate School of Information Science and Technology, The University of Tokyo

• HIRAISHI Hidefumi

  Graduate School of Information Science and Technology, The University of Tokyo

• IMAI Hiroshi

  Graduate School of Information Science and Technology, The University of Tokyo

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^*(Bell_{min{pw}+1,ppw}}), where Bell_n 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 Bell_{n-O(n/log n)}.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102.A (9), 1022-1027, 2019-09-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• BDD
• Tutte polynomial
• graph
• pathwidth
• FPT algorithm

Details

• CRID: 1390001277344478848
• NII Article ID: 130007699447
• DOI: 10.1587/transfun.e102.a.1022
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E102.A/9/E102.A_1022/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed