Algorithms for some graph problems on a distributed computational model

DOI10.1016/0020-0255(87)90039-9zbMath0626.68050OpenAlexW2071155722MaRDI QIDQ580985

Pranay Chaudhuri

Publication date: 1987

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(87)90039-9

zbMATH Keywords

time complexitydistributed algorithmscommunication complexitycomplexity measuresgraph problemsnetwork model of computation

Mathematics Subject Classification ID

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

Related Items (6)

An efficient distributed bridge-finding algorithm ⋮ Fast parallel graph searching with applications ⋮ Distributed processing of graphs: Fundamental cycles algorithm ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ On the complexity of distributed graph coloring with local minimality constraints

Cites Work

• A new distributed depth-first-search algorithm
• Parallel algorithms for the single source shortest path problem
• Graph Traversal Techniques and the Maximum Flow Problem in Distributed Computation
• Graph Problems on a Mesh-Connected Processor Array
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallel Matrix and Graph Algorithms
• Efficient parallel algorithms for some graph problems
• Parallel Computations in Graph Theory

This page was built for publication: Algorithms for some graph problems on a distributed computational model