Green's theorem and isolation in planar graphs

DOI10.1016/j.ic.2012.03.002zbMath1251.05041OpenAlexW2139649317MaRDI QIDQ714498

Raghunath Tewari, N. V. Vinodchandran

Publication date: 11 October 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.03.002

zbMATH Keywords

space complexityGreenś theoremisolating lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Integral formulas of real functions of several variables (Stokes, Gauss, Green, etc.) (26B20)

Related Items (6)

Depth-first search in directed planar graphs, revisited ⋮ NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Bipartite Perfect Matching is in Quasi-NC

Cites Work

• Unnamed Item
• Unnamed Item
• Planar and grid graph reachability problems
• How to draw a planar graph on a grid
• Matching is as easy as matrix inversion
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Deterministically isolating a perfect matching in bipartite planar graphs
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Directed Planar Reachability Is in Unambiguous Log-Space
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Undirected connectivity in log-space
• On Threshold Circuits and Polynomial Computation
• Boolean complexity classes vs. their arithmetic analogs
• Making Nondeterminism Unambiguous

This page was built for publication: Green's theorem and isolation in planar graphs