Parallel recognition of series-parallel graphs

DOI10.1016/0890-5401(92)90041-DzbMath0754.68056WikidataQ29036715 ScholiaQ29036715MaRDI QIDQ1201288

David Eppstein

Publication date: 17 January 1993

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

zbMATH Keywords

nesting; CRCW model; ear decompositions; EREW model; terminal selection

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68W15: Distributed algorithms

Related Items

A Lower Bound on the Area Requirements of Series-Parallel Graphs, Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs, Analyse de sensibilité pour les problèmes linéaires en variables 0-1, Planar orientations with low out-degree and compaction of adjacency matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel recognition and decomposition of two terminal series parallel graphs
• A linear algorithm for the domination number of a series-parallel graph
• Topology of series-parallel networks
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Prefix Computation
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• The Parallel Evaluation of General Arithmetic Expressions
• Linear-time computation of optimal subgraphs of decomposable graphs