Greed is good

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Greed is good: approximating independent sets in sparse and bounded-degree graphs

Full text

Pdf (937 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: 439 - 448

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Magnús Halldórsson	School of Information Science, Japan Adv. Institute of Science and Tech., Ishikawa 923-12, Japan
Jaikumar Radhakrishnan	Theoretical Computer Science Group, Tata Institute of Fundamental Research, Bombay, India

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 44, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195221 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	M. Ajtai, J. Koml6s, and E. Szemer6di. A note on Ramsey numbers. J. Combin. Theory Set. A, 29:354-360, 1980.
	2	N. Alon and J. Spencer. The Probabilistic Method. Wiley, 1992.
	3	Piotr Berman , Martin Fürer, Approximating maximum independent set in bounded degree graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.365-371, January 23-25, 1994, Arlington, Virginia, United States
	4	Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
	5	V. Chv~tal. A greedy heuristic for the set covering problem. Math. Oper. Res., 4:233-235, 1979.
	6	V. Chvgtal. Linear Programming. Freeman, New York, 1983.
	7	P. ErdSs. On the graph theorem of Tur~n (in Hungarian). Mat. Lapok, 21:249-251, 1970.
	8	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States [doi>10.1145/28395.28429]
	9	Mark Goldberg , Thomas H. Spencer, An efficient parallel algorithm that finds independent sets of guaranteed size, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 22-24, 1990, San Francisco, California, United States
	10	M. M. Halld6rsson and j. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs. Manuscript, Feb. 1994.
	11	D. S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems. Disc. Applied Math., 6:243-254, 1983.
	12	D. S. Johnson. Worst case behavior of graph coloring algorithms. In Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Congressu8 Numerantium X, pages 513-527, 1974.
	13	S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computation views of approximabiIity. Manuscript, Dec. 1993.
	14	Burkhard Monien , Ewald Speckenmeyer, Some Further Approximation Algorithms for the Vertex Cover Problem, Proceedings of the 8th Colloquium on Trees in Algebra and Programming, p.341-349, March 09-11, 1983
	15	G. L. Nemhauser and W. T. Trotter. Vertex packing: Structural properties and algorithms. Math. Programming, 8:232-248, 1975.
	16	Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129769]
	17	V. Th. Paschos, A (&Dgr;/2)-approximation algorithm for the maximum independent set problem, Information Processing Letters, v.44 n.1, p.11-13, Nov. 9, 1992 [doi>10.1016/0020-0190(92)90248-T]
	18	J. B. Shearer. A note on the independence number of triangle-free graphs. Discrete Math., 46:83-87, 1983.
	19	James B. Shearer, Note on the independence number of triangle-free graphs, II, Journal of Combinatorial Theory Series A, v.53 n.2, p.300-307, Mar. 1990
	20	H. U. Simon. On approximate solutions for combinatorial optimization problems. SIAM J. Disc. Math., 3(2):294-310, May 1990.
	21	P. Tur~n. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48:436-452, 1941.

CITED BY 13

	Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States
	Vangelis T. Paschos, A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys (CSUR), v.29 n.2, p.171-209, June 1997
	Claudia Bertram-Kretzberg , Hanno Lefmann, The algorithmic aspects of uncrowded hypergraphs, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.296-304, January 05-07, 1997, New Orleans, Louisiana, United States
	Renu Mehra , Jan Rabaey, Exploiting regularity for low-power design, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.166-172, November 10-14, 1996, San Jose, California, United States
	Eran Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.329-337, January 09-11, 2000, San Francisco, California, United States
	Marc Demange, A Note on the Approximation of a Minimum-Weight Maximal Independent Set, Computational Optimization and Applications, v.14 n.1, p.157-169, July 1999
	Yuanqing Guo , Gerard J.M. Smit , Hajo Broersma , Paul M. Heysters, A graph covering algorithm for a coarse grain reconfigurable system, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Ryan Kastner , Seda Ogrenci-Memik , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Instruction generation for hybrid reconfigurable systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Haiyun Luo , Songwu Lu , Vaduvur Bharghavan , Jerry Cheng , Gary Zhong, A packet scheduling approach to QoS support in multihop wireless networks, Mobile Networks and Applications, v.9 n.3, p.193-206, June 2004
	Magnús M. Halldórsson , Jaikumar Radhakrishnan, Improved approximations of independent sets in bounded-degree graphs via subgraph removal, Nordic Journal of Computing, v.1 n.4, p.475-492, Winter 1994
	Gao Cong , Wenfei Fan , Floris Geerts , Xibei Jia , Shuai Ma, Improving data quality: consistency and accuracy, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Leopoldo Bertossi , Loreto Bravo , Enrico Franconi , Andrei Lopatenko, The complexity and approximation of fixing numerical attributes in databases under integrity constraints, Information Systems, v.33 n.4-5, p.407-434, June, 2008
	M. Fraiwan , G. Manimaran, Scheduling algorithms for conducting conflict-free measurements in overlay networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.15, p.2819-2830, October, 2008