Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

被引：5

作者：

Wan, Pengfei ^{[1
]}

Tu, Jianhua ^{[2
]}

Zhang, Shenggui ^{[1
]}

Li, Binlong ^{[1
]}

机构：

[1] Northwestern Polytech Univ, Dept Appl Math, Xian 710072, Shaanxi, Peoples R China

[2] Beijing Univ Chem Technol, Dept Math, Beijing 100029, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2018年 / 332卷

关键词：

Independent set; Matching; Treewidth; Dynamic programming; TOPOLOGICAL INDEX; HOSOYA INDEX; ENTROPY; COMPLEXITY; ALGORITHM; SYSTEMS;

D O I：

10.1016/j.amc.2018.03.017

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In the theory and applications of graphs, it is a basic problem to compute the numbers of independent sets and matchings of given sizes. Since the problem of computing the total number of independent sets and that of matchings of graphs is #P-complete, it is unlikely to give efficient algorithms to find the numbers of independent sets and matchings of given sizes. In this paper, for graphs with order n and treewidth at most p, we present two dynamic algorithms to compute the numbers of independent sets of all sizes with runtime O(2(p) . pn(3)) and the numbers of matchings of all sizes with runtime O(2(2p) . pn(3)), respectively. By the algorithms presented in this paper, for graphs with small treewidths, the numbers of independent sets and matchings of all possible sizes can be computed efficiently. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：42 / 47

页数：6

共 37 条

[1]

Ahmadi MB, 2014, MATCH-COMMUN MATH CO, V71, P355

[2] INDEPENDENT SETS IN REGULAR GRAPHS AND SUM-FREE SUBSETS OF FINITE-GROUPS [J].

ALON, N .

ISRAEL JOURNAL OF MATHEMATICS, 1991, 73 (02) :247-256

[3]

[Anonymous], 2015, Parameterized algorithms

[4]

[Anonymous], 2009, ENCY COMPLEXITY SYST, DOI DOI 10.1007/978-0-387-30440-3_285

[5] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[6] A linear-time ie algorithm for finding three-decompositions of small treewidth [J].

Bodlaender, HL .

SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1305-1317

[7] INFORMATION-THEORY, DISTANCE MATRIX, AND MOLECULAR BRANCHING [J].

BONCHEV, D ;

TRINAJSTIC, N .

JOURNAL OF CHEMICAL PHYSICS, 1977, 67 (10) :4517-4533

[8]

Bonchev D., 1983, INFORM THEORIETIC IN

[9]

Bondy J., 2008, GRAPH THEORY GTM 244

[10] Network Entropies Based on Independent Sets and Matchings [J].

Cao, Shujuan ;

Dehmer, Matthias ;

Kang, Zhe .

APPLIED MATHEMATICS AND COMPUTATION, 2017, 307 :265-270

← 1 2 3 4 →