ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane
Full text PdfPdf (501 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents
Montreal, Quebec, Canada
Pages: 432 - 438  
Year of Publication: 1994
ISBN:0-89791-663-8
Authors
Naveen Garg  Department of Computer Science and Engineering, Indian Institute of Technology, Delhi
Dorit S. Hochbaum  Industrial Engineering and Operations Research, University of California, Berkeley, CA
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 3,   Downloads (12 Months): 32,   Citation Count: 9
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195218
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
B. Awerbuch, Y. Azar, A. Blum and S. Vempala. Personal Communication.
 
2
G. Kortsarz and D. Peleg. "On choosing a dense subgraph". In Proceedings, 34th Annual Symposium on Foundations of Computer Science 1993.
 
3
S.S. Kavi, D.j. l#osenkrantz and G.K. Tayi. "Facility dispersion problems" Heuristics and special cases". In Proceedings, 2na Workshop on Algorithms and Data Structures 1991.
 
4
R. Ravi , R. Sundaram , M. V. Marathe , D. J. Rosenkrantz , S. S. Ravi, Spanning trees short or small, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.546-555, January 23-25, 1994, Arlington, Virginia, United States

CITED BY  9
Avrim Blum , R. Ravi , Santosh Vempala, A constant-factor approximation algorithm for the k MST problem (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.442-448, May 22-24, 1996, Philadelphia, Pennsylvania, United States
Cristian S. Mata , Joseph S. B. Mitchell, Approximation algorithms for geometric tour and network design problems (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.360-369, June 05-07, 1995, Vancouver, British Columbia, Canada
Baruch Awerbuch , Yossi Azar , Avrim Blum , Santosh Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.277-283, May 29-June 01, 1995, Las Vegas, Nevada, United States
Joseph S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.402-408, January 28-30, 1996, Atlanta, Georgia, United States
Avrim Blum , Prasad Chalasani , Santosh Vempala, A constant-factor approximation for the k-MST problem in the plane, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.294-302, May 29-June 01, 1995, Las Vegas, Nevada, United States
Baruch Awerbuch , Tripurari Singh, Online algorithms for selective multicast and maximal dense trees, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.354-362, May 04-06, 1997, El Paso, Texas, United States
Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada
Magnús M. Halldórsson , Kazuo Iwano , Naoki Katoh , Takeshi Tokuyama, Finding subsets maximizing minimum structures, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.150-159, January 22-24, 1995, San Francisco, California, United States
Naveen Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
Naveen Garg: colleagues
Dorit S. Hochbaum: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player