Daniel J. Rosenkrantz
Ph.D., Columbia UniversityLeading Professor Emeritusdjr@cs.albany.edu Computer Science Department University at Albany Albany, NY 12222 (518) 442-4270 (518) 442-5638 (FAX) |

Statement of Research |

Research interests are in algorithms, database systems, and
high-performance computing. Algorithms interests are in combinatorial optimization and network design, particularly developing approximation methods. Also algorithms for analysis, design, transformation, and optimization of various design objects, including programs, hardware, simulation models, specifications, networks, grammars, etc. Database systems interests are concurrency control, distributed databases, web databases, and data mining. This involves formalizing appropriate models for the concepts involved, and devising efficient algorithms where possible. High-performance computing interests are in compiling for distributed architectures and in algorithms for distributed systems. |

Awards |

Excellence in Research Award, University at Albany, 1991. Fellow of Association for Computing Machinery. ACM SIGMOD (Special Interest Group on Management of Data) Contributions Award, 2001. |

Selected Publications |

P. Chundi and D. J. Rosenkrantz,
,
Data Mining and Knowledge Discovery, 17, 3, Dec. 2008, 377-401.
Efficient Algorithms for Segmentation of Item-Set
Time Series |

H. Siy, P. Chundi, D. J. Rosenkrantz and M. Subramaniam,
,
J. Software Maintenance and Evolution: Research and Practice,
20, 3, May-June 2008, 199-222.
A Segmentation-Based Approach for Temporal Analysis
of Software Version Repositories |

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz, R. E. Stearns and M. Thakur,
,
Theoretical Computer Science, 386, 1-2, Oct. 2007, 3-37.Predecessor Existence Problems for Finite Discrete
Dynamical Systems |

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
J. Computer and System Sciences, 72, 8, Dec. 2006, 1317-1345.Complexity of Reachability Problems for Finite Discrete
Dynamical Systems |

D. J. Rosenkrantz, L. R. Mullin and H. B. Hunt III,
,
ACM Trans. Programming Languages and Systems, 28, 6, Nov. 2006, 1145-1177.
On Minimizing Materializations of Array-Valued
Temporaries |

P. Chundi and D. J. Rosenkrantz,
,
Data Mining and Knowledge Discovery, 13, 1, July 2006, 41-65.
Information Preserving Time Decompositions of Time Stamped
Documents |

D. J. Rosenkrantz, G. K. Tayi and S. S. Ravi,
,
Networks, 47, 4, July 2006, 206-217.
Obtaining Online Approximations Algorithms for Facility
Dispersion from Offline Algorithms |

H. B. Hunt III, M. V. Marathe, D. J. Rosenkrantz and R. E. Stearns,
,
Computational Complexity and Statistical Physics,
A. Percus, G. Istrate, and C. Moore (Editors),
Oxford University Press,
2006, 285-318.Towards a Predictive Computational Complexity Theory for
Periodically Specified Problems: A Survey |

P. Chundi, R. Zhang and D. J. Rosenkrantz,
,
Proc. Sixteenth Intl. Conf. on Database and Expert Systems Applications
(DEXA 2005),
Copenhagen, Denmark, Aug. 2005, 514-523.Efficient Algorithms for Constructing
Time Decompositions of Time Stamped Documents |

D. J. Rosenkrantz, S. Goel, S. S. Ravi and J. Gangolly,
,
Proc. Fifth European Dependable Computing Conf. (EDCC 05),
Budapest, Hungary, April 2005,
Lecture Notes in Computer Science, Vol. 3463, Springer, 345-362.
Structure-Based Resilience Metrics for Service-Oriented
Networks |

P. Chundi and D. J. Rosenkrantz,
,
Proc. Thirteenth Conf. on Information and Knowledge Management (CIKM 2004),
Washington, DC, Nov. 2004, 437-445.On Lossy Time Decompositions of Time Stamped
Documents |

G. K. Tayi , D. J. Rosenkrantz and S. S. Ravi,
,
European Journal of Operational Research, 157, 2, Sept. 2004, 267-285.
Local Base Station Assignment with Time Intervals in Mobile
Computing Environments |

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Annals of Combinatorics, 7, Dec. 2003, 381-408.On Some Special Classes of Sequential
Dynamical Systems |

C. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Theoretical Computer Science, 295, 1-3, Feb. 2003, 41-64.Reachability Problems for Sequential Dynamical Systems
with Threshold Functions |

H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Information and Computation, 173, 1, Feb. 2002, 40-63.Parallel Approximation Schemes for a Class of Planar and
Near Planar Combinatorial Optimization Problems |

R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz
and H. B. Hunt III,
,
Algorithmica, 31, 1, May 2001, 58-78.Approximation Algorithms for Degree-Constrained
Minimum-Cost Network-Design Problems |

D. J. Rosenkrantz, L. Yu and S. S. Ravi,
,
Algorithmica, 30, 1, Jan. 2001, 83-100.Efficient Construction of Minimum Makespan Schedules for
Tasks with a Fixed Number of Distinct Execution Times |

K. B. Lakshmanan, D. J. Rosenkrantz and S. S. Ravi,
,
Theoretical Computer Science, 243, 1-2, July 2000, 269-288.Alarm Placement in Systems with
Fault Propagation |

D. J. Rosenkrantz, G. K. Tayi and S. S. Ravi,
,
INFORMS Journal on Computing, 12, 2, Spring 2000, 136-149.Algorithms for Path-Based Placement of Inspection Stations
on Networks |

D. J. Rosenkrantz, G. K. Tayi and S. S. Ravi,
,
J. Combinatorial Optimization, 4, 1, March 2000, 7-33.Facility Dispersion Problems Under Capacity and
Cost Constraints |

G. K. Tayi, D. J. Rosenkrantz and S. S. Ravi,
,
Networks, 34, 8, Aug. 1999, 19-35.Path Problems in Networks with
Vector-Valued Edge Weights |

R. Narasimhan, D. J. Rosenkrantz and S. S. Ravi,
,
Intl. J. Parallel Programming, 27, 4, Aug. 1999, 289-323.Using Data Flow Information to Obtain Efficient Check Sets
for Algorithm-Based Fault Tolerance |

M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi,
D. J. Rosenkrantz and H. B. Hunt III,
,
Journal of Algorithms, 28, 1, July 1998, 142-171.Bicriteria Network Design Problems |

H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Journal of Algorithms, 26, 2, Feb. 1998, 238-274.NC-Approximation Schemes for NP- and PSPACE-Hard
Problems for Geometric Graphs |

S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan,
S. S. Ravi and D. J. Rosenkrantz,
,
Theoretical Computer Science, 181, 2, July 1997, 379-404.Compact Location Problems |

R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz and S. S. Ravi,
,
SIAM Journal on Discrete Mathematics, 9, 2, May 1996, 178-200.Spanning Trees - Short or Small |

Y. Breitbart, H. B. Hunt III and D. J. Rosenkrantz,
,
Theoretical Computer Science, 145, 1-2, July 1995, 45-69.On the Size of Binary Decision Diagrams Representing
Boolean Functions |

D. Gu, D. J. Rosenkrantz and S. S. Ravi,
,
IEEE Trans. Computers, 43, 6, June 1994, 641-650.Construction of Check Sets for Algorithm-Based
Fault Tolerance |

L. Yu and D. J. Rosenkrantz,
,
ACM Trans. Programming Languages and Systems, 16, 3,
May 1994, 775-797.A Linear-Time Scheme for Version Reconstruction |

D. J. Rosenkrantz and H. B. Hunt III,
, SIAM
Journal on Computing, 22, 3, June 1993, 627-649.The Complexity of Processing Hierarchical Specifications |

D. J. Rosenkrantz and S. S. Ravi,
,
IEEE Trans. Computers, 42, 5, May 1993, 630-635.Improved Bounds for Algorithm Based Fault-Tolerance |

D. Gu, D. J. Rosenkrantz and S. S. Ravi,
, J. Parallel and Distributed Computing, 18, 1, May 1993, 56-70. Determining Performance Measures of Algorithm-Based Fault Tolerant
Systems |

L. Yu and D. J. Rosenkrantz,
,
IEEE Transactions on Knowledge and Data Engineering, 5, 2, April 1993, 352-362.Ancestor Controlled Submodule Inclusion in Design Databases |

L. Yu and D. J. Rosenkrantz,
, SIAM
Journal on Computing, 21, 5, Oct. 1992, 824-855. Representability
of Design Objects by Ancestor-Controlled Hierarchical Specifications |

P. J. Bernhard and D. J. Rosenkrantz,
, J. Parallel and
Distributed Computing, 11, 1, Jan. 1991, 72-85.An Efficient Method for Representing and Transmitting
Message Patterns on Multiprocessor Interconnection Networks |

D. J. Rosenkrantz and H. B. Hunt III,
, ACM Trans. Programming Languages and Systems, 9, 4, Oct.
1987, 543-566.Efficient Algorithms for Automatic Construction and Compactification of
Parsing Grammars |

H. B. Hunt and D. J. Rosenkrantz,
, SIAM Journal on Computing, 15, 3, Aug. 1986, 831-850.
Recursion Schemes and Recursive Programs are Exponentially
Hard to Analyze |

P. A. Bloniarz, H. B. Hunt and D. J. Rosenkrantz,
, J. Assoc. Computing Mach., 31, 4, Oct. 1984, 879-904.Algebraic Structures with Hard Equivalence and Minimization
Problems |

D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis,
, SIAM Journal on Computing, 13, 3, Aug. 1984, 508-530.Consistency and Serializability of
Concurrent Database Systems |

D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis,
,
ACM Trans. Database Systems, 3, 2, June 1978, 178-198.System Level Concurrency Control for Distributed Database Systems |

D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis,
,
SIAM Journal on Computing, 6, 3, Sept. 1977, 563-581.An Analysis of Several Heuristics for the Traveling Salesman Problem |

P. M. Lewis, D. J. Rosenkrantz and R. E. Stearns,
,
Addison Wesley Publishing Co., 1976.Compiler Design Theory |