Name
Abstract | ||
|---|---|---|
Given a graph with vertices, terminals and positive integer weights not larger than , we compute a minimum in time and space, where the notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give -time polynomial space algorithms for , and # with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the of a graph, and counting the number of perfect matchings of a graph. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00453-012-9630-x | Algorithmica |
Keywords | Field | DocType |
Inclusion-Exclusion,Fixed parameter tractability,Exact algorithms,Polynomial space,Steiner tree | Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Polynomial,Steiner tree problem,Algorithm,Regular polygon,Spanning tree,Degree-constrained spanning tree,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
65 | 4 | 0178-4617 |
Citations | PageRank | References |
21 | 0.81 | 19 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesper Nederlof | 1 | 294 | 24.22 |