Parallel recognition and decomposition of two terminal series parallel graphs

DOI10.1016/0890-5401(87)90061-7MaRDI QIDQ1098313zbMATH OpenOpenAlexFDO

Authors Xin He, Yaacov Yesha

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0890-5401(87)90061-7

zbMATH Keywords

acyclic graphdecomposition treeparallel algorithmtwo terminal series parallel graphs

Mathematics Subject Classification ID

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

Review text

In this paper, we develop a parallel recognition and decomposition algorithm for two-terminal series parallel (TTSP) graphs. Given a directed acyclic graph G in edge list form, the algorithm determines whether G is a TTSP graph. If G is a TTSP graph, the algorithm constructs a decomposition tree for G. Some interesting properties of the TTSP graphs are derived in order to facilitate fast parallel processing. The algorithm runs in \(O(\log^ 2 n+\log m)\) time with \(O(n+m)\) processors on an exclusive read exclusive write PRAM where n (m) is the number of vertices (edges) in G. This algorithm is within a polylogarithmic factor of optimal.

Recommendations

• Parallel algorithms for series parallel graphs
• Publication:4489178
• scientific article; zbMATH DE number 1107730
• Parallel recognition of series-parallel graphs
• Computational Science - ICCS 2004

Cites work

• Linear-time computability of combinatorial problems on series-parallel graphs
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Topology of series-parallel networks

Cited in

(12)

• Planar orientations with low out-degree and compaction of adjacency matrices
• Parallel recognition of series-parallel graphs
• Efficient parallel recognition of some circular arc graphs. I
• A note on the tour problems in two-terminal series-parallel graphs
• An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs
• Binary tree algebraic computation and parallel algorithms for simple graphs
• scientific article; zbMATH DE number 1472126 (Why is no real title available?)
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Monotonicity of equilibria in nonatomic congestion games
• Efficient parallel recognition of some circular arc graphs. II
• Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling
• Parallel recognition of complement reducible graphs and cotree construction

This page was built for publication: Parallel recognition and decomposition of two terminal series parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098313)