Name
Abstract | ||
|---|---|---|
We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. On the other hand, we show that for any other modulus and in the non-modular case, our problem is as hard in the planar case as for the case of arbitrary graphs. This completely settles the question regarding the complexity of modular computation of the number of spanning trees in planar graphs. The techniques used rely heavily on algebraic-topology. In the spirit of counting problems modulo 2^k, we also exhibit a highly parallel \oplusL algorithm for finding the value of a Permanent modulo 2^k. Previously, the best known result in this direction was Valiant's result that this problem lies in P. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/CCC.2007.23 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | DocType | Volume |
planar case,parity problems,modular computation,known result,planar graphs,modular setting,planar graph,constant k,non-modular case,problems modulo,arbitrary graph,permanent modulo,bipartite graph,computational complexity,algebra,parallel algorithms,mathematics,computer science,spanning trees,pervasive computing,algebraic topology,polynomials,parallel algorithm,tree graphs,spanning tree | Conference | 14 |
Issue | ISSN | ISBN |
035 | 1093-0159 | 0-7695-2780-9 |
Citations | PageRank | References |
4 | 0.57 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Braverman | 1 | 810 | 61.60 |
| Raghav Kulkarni | 2 | 172 | 19.48 |
| Sambuddha Roy | 3 | 219 | 19.23 |