Sotabase

Career

· Professor, University of Waterloo

Publications (58)

Relations between concurrent-write models of parallel computation
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing · 1984
180
cited
Detecting Backdoor Sets with Respect to Horn and Binary Clauses
International Conference on Theory and Applications of Satisfiability Testing · 2004
95
cited
The Parallel Simplicity of Compaction and Chaining
J. Algorithms · 1990
93
cited
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems
Algorithmica · 2004
92
cited
On Graph Powers for Leaf-Labeled Trees
Scandinavian Workshop on Algorithm Theory · 2000
90
cited
On the Parameterized Complexity of Layered Graph Drawing
Algorithmica · 2001
89
cited
Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth
Journal of computer and system sciences (Print) · 1998
71
cited
Parallel Algorithms with Processor Failures and Delays
J. Algorithms · 1996
66
cited
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
Journal of computer and system sciences (Print) · 2004
55
cited
Incomparability in parallel computation
28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · 1987
50
cited
A bidirectional shortest-path algorithm with good average-case behavior
Algorithmica · 1989
49
cited
One, two, three . . . infinity: lower bounds for parallel computation
Symposium on the Theory of Computing · 1985
49
cited
Solving #SAT using vertex covers
Acta Informatica · 2006
46
cited
Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
Discrete Applied Mathematics · 2001
45
cited
A Fixed-Parameter Approach to 2-Layer Planarization
Algorithmica · 2001
43
cited
Perfect hashing, graph entropy, and circuit complexity
Proceedings Fifth Annual Structure in Complexity Theory Conference · 1990
33
cited
On-line target searching in bounded and unbounded domains
1996
32
cited
Linear-Size Constant-Depth Polylog-Treshold Circuits
Information Processing Letters · 1991
27
cited
On the parameterized complexity of the generalized rush hour puzzle
Canadian Conference on Computational Geometry · 2003
25
cited
The Parallel Complexity of Element Distinctness is Omega (sqrt(log n))
SIAM Journal on Discrete Mathematics · 1988
21
cited
Sotabase
Prabhakar Ragde | Researcher Profile | Sotabase | Sotabase