Parallel Graph Algorithms that Are Efficient on Average

The following three problems concerning random graphs can be solved in (log n)O(1) expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

Authors

• Don Coppersmith
• Prabhakar Raghavan
• Martin Tompa

Keywords

• Algorithm design and analysis
• Parallel algorithms
• H infinity control
• Polynomials
• Color
• Computational modeling
• Circuit analysis computing
• Concurrent computing
• Phase change random access memory
• Computational Model
• Independent Set
• Sequential Algorithm
• Random Graph
• Lexicographic
• Almost Surely
• Maximal Set
• Parallel Algorithm
• Maximum Independent Set
• Hamiltonian Path
• Parallelization
• Undirected
• Obvious Way
• Probability 1
• Arbitrary Graph