Name
Abstract | ||
|---|---|---|
Viewing the computation of the determinant and the permanent of integer matrices as combinatorial problems on associated graphs, we explore the restrictiveness of planarity on their complexities and show that both problems remain as hard as in the general case, that is, GapL- and P- complete. On the other hand, both bipartite planarity and bimodal planarity bring the complexity of permanents down (but no further) to that of determinants. The permanent or the determinant modulo 2 is complete for ⊕L, and we show that parity of paths in a layered grid graph (which is bimodal planar) is also complete for this class. We also relate the complexity of grid graph reachability to that of testing existence/uniqueness of a perfect matching in a planar bipartite graph. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1714450.1714453 | ACM Transactions on Computation Theory (TOCT) |
Keywords | DocType | Volume |
planarity,bipartite graphs,bimodal planarity,grid graph reachability,planar bipartite graph,counting classes,bimodal planar,combinatorial problem,general case,determinant,determinant modulo,permanent,layered grid graph,associated graph,perfect matching,bipartite planarity,bipartite graph | Conference | 1 |
Issue | ISSN | ISBN |
3 | 0302-9743 | 3-540-74509-2 |
Citations | PageRank | References |
8 | 0.53 | 34 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Datta | 1 | 200 | 19.82 |
| Raghav Kulkarni | 2 | 172 | 19.48 |
| Nutan Limaye | 3 | 134 | 20.59 |
| Meena Mahajan | 4 | 688 | 56.90 |