Name
Title | ||
|---|---|---|
Fast Exponential-Time Algorithms For The Forest Counting And The Tutte Polynomial Computation In Graph Classes |
Abstract | ||
|---|---|---|
We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O*(1.8494(m)) time for 3-regular graphs, and O*(1.9706(m)) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1142/S0129054109006437 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
chordal graph, exponential-time algorithm, forest, regular graph, Tutte polynomial, unit interval graph | Tutte 12-cage,Discrete mathematics,Combinatorics,Indifference graph,Interval graph,Tutte polynomial,Chordal graph,Algorithm,Chromatic polynomial,Pathwidth,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
20 | 1 | 0129-0541 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heidi Gebauer | 1 | 83 | 11.07 |
| Yoshio Okamoto | 2 | 79 | 6.59 |