Selected publications of Balaji Raghavachari

Selected Publications of Balaji Raghavachari

Copyright Notice: Most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes without the written permission from the respective publishers.

2008

DOMINE: A database of protein domain interactions,
B. Raghavachari, A. Tasneem, T.M. Przytycka, and R. Jothi,
Nucleic Acids Research, Vol 36 (Database Issue), D656-661, 2008. [PDF] [Text] [Database Website]

2007

A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity,
P. Gubbala, and B. Raghavachari,
Proceedings of the Workshop on Algorithms and Data Structures (WADS), Halifax, Canada, August 2007, pages 39-51.

Approximating the k-traveling repairman problem with repairtimes,
Raja Jothi and Balaji Raghavachari
Journal of Discrete Algorithms, 5(2): 293-303 (2007), Elsevier Press.

Greedy Methods,
Samir Khuller, Balaji Raghavachari, and Neal Young,
Chapter 4 in ``Approximation Algorithms and Metaheuristics,'' Teofilo F. Gonzalez (ed.), Chapman & Hill/CRC, 2007.

2006

Load balanced agent activation for value added network services,
C. Gong, K. Sarac, O. Daescu, B. Raghavachari, and R. Jothi,
Computer Communications, Volume 29, Number 11, pages 1905-1916, Elsevier Press, July 2006.

2005

Approximation algorithms for the minimum cardinality two-connected spanning subgraph problem,
Prabhakar Gubbala and Balaji Raghavachari,
Proceedings of the Eleventh Conference on Integer Programming and Combinatorial Optimization (IPCO), Berlin, Jun 8-10, 2005, pages 422-436.

Towards intelligent services: a case study in chemical emergency response,
A. Bansal, K. Patel, G. Gupta, B. Raghavachari, J. Staves, and D. Harris,
Proceedings of the International Conference on Web Services, IEEE Press, Jun 2005, pages 751-758.

Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design,
Raja Jothi and Balaji Raghavachari,
ACM Transactions on Algorithms, ACM Press, Volume 1, Number 2, pages 265-282, 2005.

Dual-homing protection in IP-over-WDM networks,
Jianping Wang, Vinod Vokkarane, Raja Jothi, Xiangtong Qi, Balaji Raghavachari, and Jason Jue
IEEE/OSA Journal of Lightwave Technology, Vol. 23, No. 10, pages 3111-3124, October 2005.

2004

Approximation algorithms for finding low-degree subgraphs,
P. N. Klein, R. Krishnan, B. Raghavachari, and R. Ravi,
Networks, Volume 44, Number 3, pages 203-215, 2004.
Load-Balanced for reliable multicast,
C. Gong, O. Daescu, R. Jothi, B. Raghavachari, and K. Sarac,
in Proc. 3rd IASTED Intl. Conference on Communications, Internet, and Information Technology (CIIT), US Virgin Islands, Nov 22-24, 2004.
Protein folding in hydrophobic-hydrophilic model: How good is theory in practice?
R. Jothi and B. Raghavachari,
Poster Presentation at the 7th Annual Conference on Computational Genomics (CG), Reston, VA, Oct 21-24, 2004.
Degree-bounded minimum spanning trees,
R. Jothi and B. Raghavachari,
in Proc. 16th Canadian Conference on Computational Geometry (CCCG), pp. 192-195, Montreal, Canada, Aug 9-11, 2004.
Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design,
R. Jothi and B. Raghavachari,
in Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP),
pp. 805-818, Springer-Verlag LNCS 3142, Turku, Finland, July 12-16, 2004.
Improved approximation algorithms for the single-sink buy-at-bulk network design problems,
R. Jothi and B. Raghavachari,
in Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT),
pp. 336-348, Springer-Verlag LNCS 3111, Humlebaek, Denmark, July 8-10, 2004.
Dynamic Dual-homing protection in WDM mesh networks,
V. Vokkarane, J. Wang, R. Jothi, X. Qi, B. Raghavachari, and J. Jue
in Proc. IEEE International Conference on Communications (ICC),
Vol. 3, pp. 1644-1648, Paris, France, June 20-24, 2004.
Minimum latency tours and the k-traveling repairman problem,
R. Jothi and B. Raghavachari,
in Proc. Latin American Theoretical INformatics (LATIN),
Springer-Verlag LNCS 2976, pp. 423-433, Buenos Aires, Argentina, April 4-9, 2004.
Finding k-Connected subgraphs with minimum average weight,
P. Gubbala and B. Raghavachari,
in Proc. Latin American Theoretical INformatics (LATIN),
Springer-Verlag LNCS 2976, pp. 212-221, Buenos Aires, Argentina, April 4-9, 2004.
Optimal placement of NAK suppressing agents for reliable multicast: a partial deployment case,
O. Daescu, R. Jothi, B. Raghavachari, and K. Sarac
in Proc. 19th ACM Symposium on Applied Computing (SAC),
Nicosia, Cyprus, March 14-17, pp. 334-338, 2004.
Survivable network design: the capacitated minimum spanning network problem,
R. Jothi and B. Raghavachari
in Proc. 7th INFORMS Telecommunications Conference (Telecom), Boca Raton, Florida, March 7-10, pp. 50-52, 2004.
Journal version of this paper appeared in Information Processing Letters, Vol. 91(4), pp. 183-190, 2004.
Multi-homing protection in WDM mesh networks,
K. Deen, R. Jothi and B. Raghavachari
in Proc. 7th INFORMS Telecommunications Conference (Telecom), Boca Raton, Florida, March 7-10, 2004.
Revisiting Esau-Williams' algorithm: on the design of local access networks,
R. Jothi and B. Raghavachari
in Proc. 7th INFORMS Telecommunications Conference (Telecom), Boca Raton, Florida, March 7-10, pp. 104-107, 2004.
Placement of proxy servers to support server-based reliable multicast,
R. Jothi and B. Raghavachari,
in Proc. 3rd IEEE International Conference on Networking (ICN),
ISBN 0-86341-326-9, French Caribbean, Feb 29-Mar 4, 2004.
Dynamic capacitated minimum spanning trees,
R. Jothi and B. Raghavachari
in Proc. 3rd IEEE International Conference on Networking (ICN),
ISBN 0-86341-326-9, French Caribbean, Feb 29-Mar 4, 2004.

2003

Design of local access networks,
R. Jothi and B. Raghavachari,
in Proc. 15th IASTED Intl. Conf. on Parallel and Distributed Computing and Systems (PDCS),
Marina Del Ray, CA, Nov 3-5, pages 883-888, 2003.

Leave no stone unturned: improved approximation algorithm for degree-bounded minimum spanning trees,
R. Jothi and B. Raghavachari,
DIMACS Workshop on Geometric Optimization, New Brunswick, NJ, May 19-21, 2003.

A 5/4-approximation algorithm for minimum 2-edge-connectivity,
R. Jothi, B. Raghavachari and S. Varadarajan,
in Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA),
ACM Press, pages 725-734, Baltimore, MD, Jan 12-14, 2003.

2001

The directed minimum-degree spanning tree problem,
R. Krishnan and B. Raghavachari,
In the Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2001.
Algorithms for capacitated vehicle routing,
M. Charikar, S. Khuller and B. Raghavachari,
SIAM Journal on computing, Volume 31, Number 3, pages 665 - 682, 2001.

2000

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem,
N. Guttmann-Beck, R. Hassin, S. Khuller and B. Raghavachari,
Algorithmica, Volume 28, pages 422-437, 2000.

1999

Approximation algorithms for the asymmetric postman problem,
B. Raghavachari and J. Veerasamy,
In the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999.
A uniform framework for approximating weighted connectivity problems (short paper),
S. Khuller, B. Raghavachari and A. Zhu,
In the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999.
Approximation algorithms for mixed postman problem,
B. Raghavachari and J. Veerasamy,
SIAM Journal on Discrete Mathematics, Volume 12, Number 4, pages 425-433, 1999.

1998

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem,
N. Guttmann-Beck, R. Hassin, S. Khuller and B. Raghavachari,
In the Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 6-17, 1998.
The finite capacity dial-a-ride problem,
M. Charikar and B. Raghavachari,
In the Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 458-467, 1998.
Approximation algorithms for mixed postman problem,
B. Raghavachari and J. Veerasamy,
In the Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 169-179, 1998.
Algorithms for capacitated vehicle routing,
M. Charikar, S. Khuller and B. Raghavachari,
In the Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pages 458-467, 1998.

1997

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees,
S. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari and N. Young,
Journal of Algorithms, Volume 24, pages 310-324, 1997.
The e-mail gossip number and the connected domination number,
F. Harary and B. Raghavachari,
Applied Mathematics Letters, Volume 10, Number 4, pages 15-17, 1997.
Graph and Network Algorithms,
S. Khuller and B. Raghavachari,
In "The Computer Science and Engineering handbook," Allen B. Tucker (ed.), CRC Press Inc., pages 203-225, 1997.

1996

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees,
S. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari and N. Young,
In the Proceedings of the 4th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 105-117, 1996.
Parallel edge coloring approximation,
M. Furer and B. Raghavachari,
Parallel Processing Letters, Volume 6, Number 3, pages 321-329, 1996.
Landmarks in graphs,
S. Khuller, B. Raghavachari and A. Rosenfeld,
Discrete Applied Mathematics, Volume 70, Number 3, pages 217-229, 1996.
Improved Approximation Algorithms for Uniform Connectivity Problems,
S. Khuller and B. Raghavachari,
Journal of Algorithms, Volume 21, pages 434-450, 1996.
On Strongly Connected Digraphs with Bounded Cycle Length,
S. Khuller, B. Raghavachari and N. Young,
Discrete Applied Mathematics, Volume 69, Number 3, pages 281-289, 1996.
Low degree spanning trees of small weight,
S. Khuller, B. Raghavachari and N. Young,
SIAM Journal on Computing, Volume 25, pages 355-368, 1996.
Algorithms for Finding Low Degree Structures,
B. Raghavachari,
In "Approximation algorithms," Dorit Hochbaum (ed.), PWS Publishers Inc., pages 266-295, 1996.
Graph and Network Algorithms,
S. Khuller and B. Raghavachari,
ACM Computing Surveys, Volume 28, No. 1, pages 43-45, 1996.

1995

Improved Approximation Algorithms for Uniform Connectivity Problems,
S. Khuller and B. Raghavachari,
In the Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pages 1-10, 1995.
Approximating the minimum equivalent digraph,
S. Khuller, B. Raghavachari and N. Young,
SIAM Journal on Computing, Volume 24, pages 859-872, 1995.
Balancing minimum spanning and shortest path trees,
S. Khuller, B. Raghavachari and N. Young,
Algorithmica, Volume 14, pages 305-321, 1995.
An efficient NC algorithm for finding Hamiltonian cycles in dense directed graphs,
M. Furer and B. Raghavachari,
Journal of Algorithms, Volume 18, pages 203-220, 1995.

1994

Low degree spanning trees of small weight,
S. Khuller, B. Raghavachari and N. Young,
In the Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 412-421, 1994.
Approximating the minimum equivalent digraph,
S. Khuller, B. Raghavachari and N. Young,
In the Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994.
Approximating the minimum degree Steiner tree to within one of optimal,
M. Furer and B. Raghavachari,
Journal of Algorithms, Volume 17, pages 409-423, 1994.
Optimal parallel algorithms for straight-line grid embeddings of planar graphs,
M-Y. Kao, M. Furer, X. He and B. Raghavachari,
SIAM Journal of Discrete Mathematics, Volume 7, pages 632-646, 1994.
Designing multi-commodity flow trees,
S. Khuller, B. Raghavachari and N. Young,
Information Processing Letters, Volume 50, pages 49-55, 1994.
Constructing aligned sequence blocks,
W. Miller, M. Boguski, B. Raghavachari, Z. Zhang and R. C. Hardison,
Journal of Computational Biology, Volume 1, pages 51-64, 1994.
Chaining multiple-aligned blocks,
Z. Zhang, B. Raghavachari, R. C. Hardison and W. Miller,
Journal of Computational Biology, Volume 1, pages 217-226, 1994.

1993
Balancing minimum spanning and shortest path trees,
S. Khuller, B. Raghavachari and N. Young,
In the Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993.
Designing multi-commodity flow trees,
S. Khuller, B. Raghavachari and N. Young,
In the Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS), 1993.

1992
Approximation Through Local Optimality: Designing Networks with Small Degree,
R. Ravi, B. Raghavachari and P. Klein,
In the Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 279-290, 1992

Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree,
M. Furer and B. Raghavachari,
In the Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 317-324, 1992.

O(n log log n)-Work Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs,
M. Furer, X He, M-Y Kao, B. Raghavachari,
In the Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 410-419, 1992.

This page was last updated on February 28, 2008.
Return to Balaji Raghavachari's home page.