Efficiently parallelizable problems on a class of decomposable graphs

DOI10.1016/j.jcss.2004.08.003zbMath1156.68508OpenAlexW2061700222MaRDI QIDQ1765226

Sun-Yuan Hsieh

Publication date: 23 February 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.08.003

zbMATH Keywords

Parallel algorithmsPRAMRooted treesSeries-parallel graphsDecomposable graphsSubgraph optimization problems

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Regularity and locality in \(k\)-terminal graphs
• Efficient parallel algorithms for series parallel graphs
• Binary tree algebraic computation and parallel algorithms for simple graphs
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• A simple parallel tree contraction algorithm
• Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
• Parallel algorithms for series parallel graphs and graphs with treewidth two

This page was built for publication: Efficiently parallelizable problems on a class of decomposable graphs