| 2010 | GLOBECOM | A Threat-Aware Routing Algorithm for Maximum Physical-Layer Path Survivability. | Shengli Yuan, Balaji Raghavachari, Lei Chen |
| 2010 | ICCCN | Finding Maximum Reliable Path in Mesh Networks under Multiple Failures. | Shengli Yuan, Balaji Raghavachari, Ankitkumar Patel |
| 2007 | WADS | A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity. | Prabhakar Gubbala, Balaji Raghavachari |
| 2005 | IPCO | Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem. | Prabhakar Gubbala, Balaji Raghavachari |
| 2004 | ICALP | Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design. | Raja Jothi, Balaji Raghavachari |
| 2004 | LATIN | Finding k-Connected Subgraphs with Minimum Average Weight. | Prabhakar Gubbala, Balaji Raghavachari |
| 2004 | LATIN | Minimum Latency Tours and the k-Traveling Repairmen Problem. | Raja Jothi, Balaji Raghavachari |
| 2004 | SAC | Optimal placement of NAK-suppressing agents for reliable multicast: a partial deployment case. | Ovidiu Daescu, Raja Jothi, Balaji Raghavachari, Kamil Sara |
| 2003 | SODA | A 5/4-approximation algorithm for minimum 2-edge-connectivity. | Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan |
| 1999 | SODA | A Uniform Framework for Approximating Weighted Connectivity Problems. | Samir Khuller, Balaji Raghavachari, An Zhu |
| 1999 | SODA | Approximation Algorithms for the Asymmetric Postman Problem. | Balaji Raghavachari, Jeyakesavan Veerasamy |
| 1998 | FOCS | The Finite Capacity Dial-A-Ride Problem. | Moses Charikar, Balaji Raghavachari |
| 1998 | IPCO | Approximation Algorithms for the Mixed Postman Problem. | Balaji Raghavachari, Jeyakesavan Veerasamy |
| 1998 | STOC | Algorithms for Capacitated Vehicle Routing. | Moses Charikar, Samir Khuller, Balaji Raghavachari |
| 1996 | IPCO | A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. | Sndor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal E. Young |
| 1995 | STOC | Improved approximation algorithms for uniform connectivity problems. | Samir Khuller, Balaji Raghavachari |
| 1994 | SODA | Approximating the Minimum Equivalent Diagraph. | Samir Khuller, Balaji Raghavachari, Neal E. Young |
| 1994 | STOC | Low degree spanning trees of small weight. | Samir Khuller, Balaji Raghavachari, Neal E. Young |
| 1993 | SODA | Balancing Minimum Spanning and Shortest Path Trees. | Samir Khuller, Balaji Raghavachari, Neal E. Young |
| 1993 | WADS | Designing Multi-Commodity Flow Trees. | Samir Khuller, Balaji Raghavachari, Neal E. Young |
| 1992 | SODA | Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree. | Martin Frer, Balaji Raghavachari |
| 1992 | SPAA | O(n log log n)-Work Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs. | Martin Frer, Xin He, Ming-Yang Kao, Balaji Raghavachari |