An optimal parallel algorithm for planar cycle separators

DOI10.1007/BF01192047zbMATH Open0830.68057OpenAlexW2047198574WikidataQ57761204 ScholiaQ57761204MaRDI QIDQ1900892FDOQ1900892

Kentaro Toyama, Ming-Yang Kao, Shang-Hua Teng

Publication date: 25 October 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01192047

Recommendations

• Improved parallel depth-first search in undirected planar graphs
• A linear-processor algorithm for depth-first search in planar graphs
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• scientific article
• Optimal parallel algorithms on planar graphs

zbMATH Keywords

optimal parallel algorithmcycle separatorplanar undirected graph

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to algorithms.
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• A linear-processor algorithm for depth-first search in planar graphs
• Parallel Depth-First Search in General Directed Graphs
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• Parallel Prefix Computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster optimal parallel prefix sums and list ranking
• Planar Strong Connectivity Helps in Parallel Depth-First Search
• Title not available (Why is that?)
• Parallel Tree Contraction Part 2: Further Applications
• Finding small simple cycle separators for 2-connected planar graphs
• A random NC algorithm for depth first search
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Optimal parallel algorithms on planar graphs
• A simple parallel tree contraction algorithm
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• Deterministic parallel list ranking
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Finding Euler tours in parallel
• Parallel algorithms for planar graph isomorphism and related problems
• Title not available (Why is that?)
• Efficient parallel algorithms for series parallel graphs
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

Cited In (11)

• Parallel algorithms for planar graph isomorphism and related problems
• A parallel approach to the Eulerian cycle problem
• Title not available (Why is that?)
• An optimal algorithm for extracting the regions of a plane graph
• A linear-processor algorithm for depth-first search in planar graphs
• Title not available (Why is that?)
• Improved parallel depth-first search in undirected planar graphs
• I/O-Efficient Planar Separators
• Fast and compact planar embeddings
• Parallel Depth-First Search in General Directed Graphs
• Title not available (Why is that?)

This page was built for publication: An optimal parallel algorithm for planar cycle separators

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