Parallel recognition of series-parallel graphs

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

Publication date: 17 January 1993

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

Full work available at URL: https://doi.org/10.1016/0890-5401(92)90041-d

zbMATH Keywords

nesting CRCW model ear decompositions EREW model terminal selection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items

Computing volumes of adjacency polytopes via Draconian sequences ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ A Lower Bound on the Area Requirements of Series-Parallel Graphs ⋮ Optimizing adiabatic quantum program compilation using a graph-theoretic framework ⋮ Exact square coloring of subcubic planar graphs ⋮ On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty ⋮ Negative prices in network pricing games ⋮ A characterization of some graphs with metric dimension two ⋮ Scheduling series-parallel task graphs to minimize peak memory ⋮ All longest cycles in a 2‐connected partial 3‐tree share a common vertex ⋮ Treelength of series-parallel graphs ⋮ Partition dimension of certain classes of series parallel graphs ⋮ $K_4$-expansions have the edge-Erdős-Pósa property ⋮ Joins, ears and Castelnuovo-Mumford regularity ⋮ Exact counting of Euler tours for generalized series-parallel graphs ⋮ DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS ⋮ Parameterized codes over graphs ⋮ Adaptivity gaps for the stochastic Boolean function evaluation problem ⋮ Algorithmic and complexity aspects of problems related to total restrained domination for graphs ⋮ A note on median eigenvalues of subcubic graphs ⋮ Unnamed Item ⋮ Cycle algebras and polytopes of matroids ⋮ The smooth structure of the moduli space of a weighted series-parallel graph ⋮ On the area of constrained polygonal linkages ⋮ The st-bond polytope on series-parallel graphs ⋮ Complexity of strict robust integer minimum cost flow problems: an overview and further results ⋮ Planar orientations with low out-degree and compaction of adjacency matrices ⋮ Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs ⋮ Regularity of the vanishing ideal over a bipartite nested ear decomposition ⋮ Broken circuit complexes of series-parallel networks ⋮ Circuit and bond polytopes on series-parallel graphs ⋮ Simplification of signal flow graphs ⋮ Unnamed Item ⋮ Series parallel linkages ⋮ The Tutte Polynomial Characterizes Simple Outerplanar Graphs ⋮ Tropical curves of hyperelliptic type ⋮ Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ A single-exponential FPT algorithm for the $K_4$-\textsc{minor cover} problem ⋮ Nowhere-Zero Flows in Signed Series-Parallel Graphs ⋮ Informational Braess’ Paradox: The Effect of Information on Traffic Congestion ⋮ Analyse de sensibilité pour les problèmes linéaires en variables 0-1 ⋮ Self-organization in many-body systems with short-range interactions: clustering, correlations and topology ⋮ $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property ⋮ On minimum average stretch spanning trees in polygonal 2-trees ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work