Planar and grid graph reachability problems
type: Item
instance of: scholarly article
title: Planar and grid graph reachability problems
zbMATH Open document ID: 1183.68409
author: David A. Mix Barrington
author: Tanmoy Chakraborty
author: Samir Datta
author: Sambuddha Roy
author: Eric Allender
published in: Theory of Computing Systems
publication date: 2009-10-19T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5617715
zbMATH Keywords: planar graphs
zbMATH Keywords: grid graphs
zbMATH Keywords: reachability
zbMATH Keywords: circuit complexity
zbMATH Keywords: logspace
zbMATH Keywords: algorithms
zbMATH Keywords: complexity theory
MaRDI profile type: Publication
full work available at URL: s00224-009-9172-z
OpenAlex ID: W2072560800
cites work: The complexity of planarity testing
cites work: Isolation, matching, and counting uniform and nonuniform upper bounds
cites work: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Directed Planar Reachability Is in Unambiguous Log-Space
cites work: The relative power of logspace and polynomial time reductions
cites work: Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
cites work: On truth-table reducibility to SAT
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: One-Input-Face MPCVP Is Hard for L, But in LogDCFL
cites work: Problems complete for deterministic logarithmic space
cites work: Planarity, Determinants, Permanents, and (Unique) Matchings
cites work: Maintenance of a minimum spanning forest in a dynamic plane graph
cites work: Counting quantifiers, successor relations, and logarithmic space
cites work: Q3757929
cites work: Faster shortest-path algorithms for planar graphs
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
cites work: Space efficient algorithms for directed series–parallel graphs
cites work: Relativization of questions about log space computability
cites work: Evaluating Monotone Circuits on Cylinders, Planes and Tori
cites work: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
cites work: Graphs on surfaces
cites work: Q4234059
cites work: Undirected ST-connectivity in log-space
cites work: Making Nondeterminism Unambiguous
cites work: The method of forced enumeration for nondeterministic automata
cites work: Q4910756
cites work: Embeddings of graphs with no short noncontractible cycles
cites work: Embedding planar graphs in four pages
DOI: 10.1007/S00224-009-9172-Z
description: scientific article; zbMATH DE number 5617715