Algorithms for some graph problems on a distributed computational model

DOI10.1016/0020-0255(87)90039-9MaRDI QIDQ580985zbMATH OpenOpenAlexFDO

Authors 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

complexity measuresdistributed algorithmscommunication complexitytime complexitygraph problemsnetwork model of computation

Mathematics Subject Classification ID

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

Recommendations

• Distributed computation on graphs
• Distributed processing of graphs: Fundamental cycles algorithm
• Fast parallel graph searching with applications
• scientific article; zbMATH DE number 3949732
• scientific article; zbMATH DE number 1810469

Cites work

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

Cited in

(12)

• Graph Labelings Derived from Models in Distributed Computing
• Derivation of a distributed algorithm for finding paths in directed networks
• Fast parallel graph searching with applications
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• An efficient distributed bridge-finding algorithm
• scientific article; zbMATH DE number 6469169 (Why is no real title available?)
• On the complexity of distributed graph coloring with local minimality constraints
• Distributed processing of graphs: Fundamental cycles algorithm
• Distributed graph algorithms and their complexity: an introduction
• A distributed algorithm for recognizing three kinds of acyclic database schemes
• scientific article; zbMATH DE number 3949732 (Why is no real title available?)
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

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

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