DR. BORIE'S RESEARCH REVIEW
My research has concentrated in the design of
algorithms for difficult graph problems that are NPhard on arbitrary graphs, but
which can be efficiently solved on certain structured classes of graphs.
Together with colleagues, we have
determined sufficient conditions such that, given a type of problem and a
structural graph property, an efficient sequential algorithm can be
automatically derived. We have also developed fast parallel algorithms for many
of the same problems, requiring only polylogarithmic time using a polynomial
number of processors. Most recently I've been working on the design of
algorithmic solutions for several variations of the pursuitevasion problem on
various graph classes.
DR. BORIE'S SELECTED PUBLICATIONS
 R. Borie, R. Parker, C. Tovey, "Recursively Constructed Graphs",
chapter 2.4 in CRC Handbook on Graph Theory (2nd edition), 2013, 101122.
 R. Parker, R. Borie, "Chinese Postman Problems", chapter 4.3 in CRC Handbook on Graph Theory (2nd edition), 2013,
284304.
 R. Borie, S. Koenig, C. Tovey, "PursuitEvasion Problems",
chapter 9.5 in CRC Handbook on Graph Theory (2nd edition), 2013, 11451164.
 R. Borie, R. Parker, C. Tovey, "Algorithms on Recursively Constructed Graphs", chapter 10.4 in CRC Handbook on Graph Theory (2nd edition), 2013,
12911313.

R. Borie, C. Tovey, S. Koenig, "Algorithms and Complexity Results for
GraphBased Pursuit Evasion", Autonomous Robots 31 (2011), 317332.

Q. Fang, M. Lei, S. Vrbsky, R. Borie, "Scheduling OnDemand Broadcast with
Timing Constraints",
Journal of Distributed and Parallel Systems 69 (2009), 737747.
 R. Borie, R. Parker, C. Tovey,
"Solving Problems on Recursively Constructed
Graphs", ACM Computing Surveys 41 (2008), article 4, 151.

R. Borie, B. Munteanu, G. Malewicz, "The Spinning Problem",
to appear.
 R. Borie, J. Johnson, V. Raghavan, J. Spinrad, "Robust Polynomial Time
Algorithms on CliqueWidth k Graphs'', to appear.

K. Chen, H. Chen, R. Borie, J. Liu,
"Mathematical Modeling and Integer Programming for File Allocation Problems in VideoonDemand Systems", to appear.
 R. Borie, R. Parker, C. Tovey, "Recursively Constructed Graphs",
chapter 2.4 in CRC Handbook on Graph Theory, 2003, 99118.
 R. Borie, R. Parker, C. Tovey, "Algorithms on Recursively Constructed Graphs", chapter 10.4 in CRC Handbook on Graph Theory, 2003,
10461066.
 S. Horton, R. Parker, R. Borie, "On Cuts of Bounded Order and the Linear
Arrangement Problem'', Discrete Applied Mathematics 103 (2000), 127139.
 R. Borie, J. Spinrad, "Construction of a Simple Elimination Scheme for a Chordal Comparability Graph in Linear Time", Discrete Applied
Mathematics 91 (1999), 287292.
Also
appears in the special volume, Discrete Applied Mathematics, Editors’
Choice (1999).

A. Parrish, R. Borie, D. Cordes, "Automated FlowgraphBased Testing of
ObjectOriented Software Modules", in Testing ObjectOriented Software,
Kung, Hsia, and Gao (editors), 1998, 6478.
 M. Kortright, R. Borie, "Applying Recursively Decomposable Graph
Techniques to NonGraph Problems'', Congressus Numerantium 134 (1998),
1134.
 M. Kortright, A Gupta, R. Borie, "Fast Parallel Algorithms for the
Balanced Decomposition of SeriesParallel Graphs'', Congressus Numerantium
134 (1998), 193218.
 A. Parrish, D. Cordes, R. Borie, S. Edara,, "Illustrating Client and
Implementation Readability Tradeoffs in Ada and C++," Software Practice
and Experience 26 (1996), 799814.
 R. Borie, "Generation of Polynomial Time Algorithms for Some
Optimization Problems on TreeDecomposable Graphs," Algorithmica 14
(1995), 123137.
 R. Borie, A. Gupta, "Balanced Decompositions for Partial
kTrees," Congressus Numerantium 98 (1993), 3338.
 R. Borie, A. Parrish, M. Srinivas, "LockandKey Strategies for
Handling Undefined Variables," Software Practice and Experience 23
(1993), 693710.
 A. Parrish, R. Borie, D. Cordes, "Automated FlowgraphBased Testing
of ObjectOriented Software Modules," Journal of Systems and Software
23 (1993), 95109.
 R. Borie, R. Parker, C. Tovey, "Automatic Generation of Linear Time
Algorithms from Predicate Calculus Descriptions of Problems on Recursively
Constructed Graph Families," Algorithmica 7 (1992), 555581.
 S. Horton, R. Parker, R. Borie, "On Some Results Pertaining to Halin
Graphs," Congressus Numerantium 89 (1992), 6587.
 R. Borie, R. Parker, C. Tovey, "Algorithms for Recognition of Regular
Properties and Decomposition of Recursive Graph Families," Annals of
Operations Research 33 (1991), 127149.
 R. Borie, R. Parker, C. Tovey, "Deterministic Decomposition of
Recursive Graph Classes," SIAM Journal of Discrete Mathematics 4
(1991), 481501.
 R. Borie, "Polynomial Time Algorithms for Recursive Graph
Classes," Congressus Numerantium 85 (1991), 219234.
 R. Borie, "Recursively Constructed Graph Families: Membership and
Linear Algorithms," Ph.D. Dissertation, Georgia Institute of Technology
(1988).