Alex Pothen
ABSTRACT
Computing a matching in a graph is one of "the hardest simple problems" in computer science. It is simple since most variants of matching can be solved in polynomial time, yet hard because the running times are high and the algorithms are complex. It is even more challenging to design parallel algorithms for matching, since many algorithms rely on searching for long paths in a graph, or implicitly communicate information along long paths, and thus have little concurrency.
Recommendations
Parallel database sorting
Sorting in database processing is frequently required through the use of Order By and Distinct clauses in SQL. Sorting is also widely known in computer science community at large. Sorting in general covers internal and external sorting. Past published ...
Derandomized Parallel Repetition via Structured PCPs
Selected papers from the 25th Annual IEEE Conference on Computational Complexity (CCC 2010)A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof and in return is allowed to err with some bounded probability. The probability that the ...
Sorting in Parallel Database Systems
HPC '00: Proceedings of the The Fourth International Conference on High-Performance Computing in the Asia-Pacific Region-Volume 2 - Volume 2Sorting in database processing is frequently required using Order By and Distinct clauses in SQL. Sorting is also widely known in computer science community at large. Sorting in general covers internal and external sorting. Past-published work has ...
Comments