Efficient computation of implicit representations of sparse graphs

DOI10.1016/S0166-218X(97)00007-3zbMath0890.68098MaRDI QIDQ1377648

Anil Maheshwari, Christos D. Zaroliagis, Srinivasa R. Arikati

Publication date: 23 June 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

parallel algorithmgraph algorithmssparse graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (3)

A Constructive Arboricity Approximation Scheme ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ Improved Dynamic Graph Coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal parallel algorithms on planar graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Faster optimal parallel prefix sums and list ranking
• Edge-Disjoint Spanning Trees of Finite Graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Symmetry-Breaking in Sparse Graphs
• Use of matroid theory in operations research, circuits and systems theory
• On Generic Rigidity in the Plane
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Optimal Parallel 5-Colouring of Planar Graphs
• Minimum partition of a matroid into independent subsets
• Decomposition of Finite Graphs Into Forests

This page was built for publication: Efficient computation of implicit representations of sparse graphs