Prabhakar Ragde's research publications

These are listed in chronological order and are complete up to September 2007. The most recent ones may be available as links from my discussion of my research interests.

Refereed journal papers

J. M. Blair, C. A. Wills, and P. L. Ragde, Rational approximation of the Bessel functions J_0(x), J_1(x), Y_0(x), Y_1(x), Mathematics of Computation, 1982.

F. E. Fich, P. L. Ragde, and A. Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal of Computing (17), 1988, pp. 606-627.

M. Luby and P. L. Ragde, A bidirectional shortest-path algorithm with good average-case behavior, Algorithmica (4), 1989, pp.551-567.

F. E. Fich, P. L. Ragde, and A. Wigderson, Simulations among concurrent-write PRAMs, Algorithmica (3), 1988, pp.43-51.

P. L. Ragde, W. Steiger, E. Szemeredi, and A. Wigderson, The parallel complexity of element distinctness is Omega(sqrt(log n)), SIAM Journal of Discrete Mathematics (1), 1988, pp.399-410.

E. Gafni, J. Naor, and P. Ragde, On separating the EREW and CREW PRAM models, Theoretical Computer Science (68), 1989, pp. 343-346.

F. E. Fich, M. Li, P. Ragde, Y. Yesha, On the power of concurrent-write PRAMs with read-only memory", Information and Computation (83), 1989, pp. 234-244.

V. Grolmusz and P. Ragde, Incomparability in parallel computation, Discrete Applied Mathematics (29), 1990, pp. 63-78.

P. Ragde and A. Wigderson, Linear-size constant-depth polylog-threshold circuits, Information Processing Letters (39), 1991, pp. 143-146.

P. Ragde, Analysis of an asynchronous PRAM algorithm, Information Processing Letters (39), 1991, pp. 253-256.

P. Ragde, Processor-time tradeoffs in PRAM simulations, Journal of Computer and Systems Sciences (44), 1992, pp. 103-113.

P. Ragde, The parallel simplicity of compaction and chaining, Journal of Algorithms (14), 1993, pp. 371-380.

F.E. Fich, M. Kowaluk, M. Kutylowski, Krzysztof Lorys, and P. Ragde, Retrieval of scattered information by EREW, CREW and CRCW PRAMs, Computational Complexity (5), 1995, pp. 113-131.

J.F. Buss, P. Kanellakis, P. Ragde, and A.A. Shvartsman, Parallel algorithms with processor delays and failures, Journal of Algorithms (20), 1996, pp. 45-86.

P. Dymond, F.E. Fich, N. Nishimura, P. Ragde, and W.L. Ruzzo, Pointers versus arithmetic in PRAMs, Journal of Computer and System Sciences (53), 1996, pp. 218-232.

O. Berkman, Y. Matias, and P. Ragde, Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs, Journal of Algorithms (28), 1998, pp. 197-215.

T. Hagerup, J. Katajainen, N. Nishimura, P. Ragde, Characterizations of multiterminal flow networks and computing flows in networks of bounded treewidth, Journal of Computer and Systems Sciences (57), 1998, pp. 366-375.

N. Nishimura, P. Ragde, D. Thilikos, Finding smallest supertrees under minor containment, International Journal of Foundations of Computer Science, 11:3, pp. 445-465, 2000.

N. Nishimura, P. Ragde, D. Thilikos, On graph powers for leaf-labeled trees, Journal of Algorithms 42:69-108, 2002.

E. D. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, D. M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, 69:166-195, 2004.

A. Gupta, N. Nishimura, A. Proskurowski, P. Ragde, Embeddings of k-connected graphs of pathwidth k, Discrete Applied Mathematics, 145:242-265, 2005.

N. Nishimura, P. Ragde, D. Thilikos, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Discrete Applied Mathematics, 152:229-245, 2005.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D.R. Wood, A fixed-parameter approach to two-layer planarization, Algorithmica, 45:159-182, 2006.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D.R. Wood, On the parameterized complexity of layered graph drawing, accepted to Algorithmica, 2007.

Papers Presented at Conferences (selection by extended abstract)

F. E. Fich, P. L. Ragde, and A. Wigderson, Relations between concurrent-write models of parallel computation (preliminary version), Proc. 3rd ACM Symp. on Principles of Distributed Computation (PODC), August 1984.

F. E. Fich, F. Meyer auf der Heide, P. L. Ragde, and A. Wigderson, One, two, three... infinity: lower bounds for parallel computation, Proc. 17th ACM Symp. on Theory of Computing (STOC), May 1985.

M. Luby and P. L. Ragde, A bidirectional shortest-path algorithm with good average-case behavior (preliminary version), Proc. 12th Intl. Conf. on Automata, Languages, and Programming (ICALP), July 1985.

V. Grolmusz and P. L. Ragde, Incomparability in parallel computation (preliminary version), Proc. 28th Annual ACM Symposium on Foundations of Computer Science (FOCS), October 1987.

I. Newman, P. L. Ragde, and A. Wigderson, Perfect hashing, graph entropy, and circuit complexity", Proc. 5th Annual IEEE Symposium on Structures in Complexity Theory (SCT), July 1990.

P. Ragde, The parallel simplicity of compaction and chaining, Proc. 17th Intl. Conf. on Automata, Languages, and Programming (ICALP), July 1990.

F.E. Fich, M. Kowaluk, M. Kutylowski, K. Lorys, P. Ragde, Retrieval of scattered information by EREW, CREW and CRCW PRAMs, Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT), July 1992.

P. Dymond, F.E. Fich, N. Nishimura, P. Ragde, and W.L. Ruzzo, Pointers versus arithmetic in PRAMs, Proc. 8th Annual IEEE Symposium on Structures in Complexity Theory (SCT), 1993.

O. Berkman, Y. Matias, and P. Ragde, Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs, Proc. 1993 Workshop on Algorithms and Data Structures, August 1993.

T. Hagerup, J. Katajainen, N. Nishimura, P. Ragde, Characterizations of k-Terminal flow networks and computing network flows in partial k-trees, Proc. 6th Annual ACM Symposium on Discrete Algorithms (SODA), January 1995.

P. Buhr, A. Goel, N. Nishimura, and P. Ragde, Parallel pointer-based join algorithms in memory mapped environments, Proc. 12th Annual International Conference on Data Engineering (ICDE), February 1996.

P. Buhr, A. Goel, N. Nishimura, and P. Ragde, uDatabase: parallelism in a memory-mapped environment (research summary), Proc. 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1996.

N. Nishimura, P. Ragde, D. Thilikos, Finding smallest supertrees under minor containment", Proc. 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), June 1999.

N. Nishimura, P. Ragde, D. Thilikos, On graph powers for leaf-labeled Trees, Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT), July 2000.

A. Gupta, N. Nishimura, P. Ragde, A. Proskurowski, Embeddings of k-Connected graphs of pathwidth k, Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT), July 2000.

N. Nishimura, P. Ragde, D. Thilikos, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Proc. 7th Workshop on Algorithms and Data Structures (WADS), August 2001.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D.R. Wood, On the parameterized complexity of layered graph drawing, Proc. 9th European Symposium on Algorithms (ESA), September 2001.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D.R. Wood, A fixed-parameter approach to two-layer planarization, Proc. 9th Conference on Graph Drawing, September 2001.

M. Hajiaghayi, N. Nishimura, P. Ragde, and D. Thilikos, Fast approximation schemes for K3,3-minor-free or K5-minor-free graphs, EuroConference on Combinatorics, Graph Theory and Applications (Comb 01), September 2001.

H. Fernau, T. Hagerup, N. Nishimura, P. Ragde, and K. Reinhardt, On the parameterized complexity of a generalized Rush Hour puzzle, Proc. 15th Canadian Conference on Computational Geometry (CCCG), August 2003.

N. Nishimura, P. Ragde, and S. Szeider, Detecting backdoor sets for Horn and binary clauses, Proc. 7th International Conference on Theory and Applications of Satisfiability (SAT 2004), May 2004.

M. R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D. M. Thilikos, and S. Whitesides, Faster fixed-parameter tractable algorithms for matching and packing problems, Proc. 12th Annual European Symposium on Algorithms (ESA 2004), September 2004.

N. Nishimura, P. Ragde, D. Thilikos, Parameterized counting algorithms for general graph covering problems, Proc. 9th Workshop on Algorithms and Data Structures (WADS 2005), August 2005.

N. Nishimura, P. Ragde, and S. Szeider, Solving #SAT using vertex covers, Proc. 9th International Conference on Theory and Applications of Satisability (SAT 2006), May 2006.