Approximating the domatic number

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating the domatic number

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 134 - 143

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Uriel Feige	Weizmann Institute, Rehovot, Israel
Magnús M. Halldórsson	Science Institute-U. Iceland, Reykjavik, Iceland and School of Informatics, Kyoto University, Japan
Guy Kortsarz	Open University, Ramat Aviv, Israel

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): 46, Citation Count: 5

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/335305.335321 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	N. Alon and J. Spencer. The Probabilistic Method. Wiley, 1992.
	2	Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
	3	J. Beck. An algorithmic approach to the Lov~sz local lemma. Random Structures and Algorithms, 2:343-365, t991.
	4	C. Berge. Balanced matrices. Math. Programming, 2:19-31, 1972.
	5	M. A. Bonucelli. Dominating sets and domatic number of circular arc graphs. Discrete Appl. Math., 12:203- 213, 1985.
	6	E. J. Cockayne and S. T. Hedetniemi. Towards a theory of domination in graphs. Networks, 7:247-261, 1997.
	7	P. Crescenzi nd V. Kann. A compendium of NP optimization problems. http://www, nada. kth. se/theory/problemlist, html, 1999.
	8	M. Farber. Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl. Math., 7:115-130, 1984.
	9	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
	10	Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
	11	S. Fujita. On the performance of greedy algorithms for finding maximum r-configurations. In Korea- Japan Joint Workshop on Algorithms and Computation (WAA C99), 1999.
	12	Satoshi Fujita , Masafumi Yamashita , Tiko Kameda, A Study on r-Configurations---A Resource Assignment Problem on Graphs, SIAM Journal on Discrete Mathematics, v.13 n.2, p.227-254, April 2000 [doi>10.1137/S0895480196311328]
	13	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	14	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
	15	T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Domination in Graphs: Advanced Topics. Marcel Dekker, 1998.
	16	T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, 1998.
	17	D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. $yst. Sci., 9:256-278, 1974.
	18	Haim Kaplan , Ron Shamir, The domatic number problem on some perfect graph families, Information Processing Letters, v.49 n.1, p.51-56, Jan. 14, 1994 [doi>10.1016/0020-0190(94)90054-X]
	19	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
	20	Jan Kratochivíl, Regular codes in regular graphs are difficult, Discrete Mathematics, v.133 n.1-3, p.191-205, Oct. 15, 1994 [doi>10.1016/0012-365X(94)90026-4]
	21	L. Lov~sz. On the ratio of optimal integral and fractional covers. Discrete Math., 13:383-390, 1975.
	22	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
	23	F. MacWilliams and N. Sloane. The Theory of Error Correcting Codes. North Holland, 1983.
	24	M. V. Marathe , H. B. Hunt, III , S. S. Ravi, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, Discrete Applied Mathematics, v.64 n.2, p.135-149, Jan. 18, 1996 [doi>10.1016/0166-218X(94)00118-W]
	25	Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
	26	M. Naor , L. J. Schulman , A. Srinivasan, Splitters and near-optimal derandomization, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.182, October 23-25, 1995
	27	A. Paz and S. Moran. Nondeterministic polynomial optimization problems and their approximations. Theoretical Comput. $ci., 15:251-277, 1981.
	28	Shen-Lung Peng , Maw-Shang Chang, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, Information Processing Letters, v.43 n.6, p.297-300, Oct. 19, 1992 [doi>10.1016/0020-0190(92)90115-C]
	29	Erez Petrank, The hardness of approximation: gap location, Computational Complexity, v.4 n.2, p.133-157, April 1994 [doi>10.1007/BF01202286]
	30	Jan Kratochvíl , Andrzej Proskurowski , Jan Arne Telle, Complexity of graph covering problems, Nordic Journal of Computing, v.5 n.3, p.173-195, Fall 1998
	31	A. S. Rao , C. P. Rangan, Linear algorithm for domatic number problem on interval graphs, Information Processing Letters, v.33 n.1, p.29-33, Oct. 1989 [doi>10.1016/0020-0190(89)90184-1]
	32	B. Zelinka. Domatic number and degree of vertices of a graph. Math. Slovaca, 33:145-147, 1983.

CITED BY 6

	Aravind Srinivasan, Domatic partitions and the Lovász local lemma, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.922-923, January 07-09, 2001, Washington, D.C., United States
	Subhash Khot, Hardness of approximating the shortest vector problem in high lp norms, Journal of Computer and System Sciences, v.72 n.2, p.206-219, March 2006
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Vincent Berry , Francois Nicolas, Improved Parameterized Complexity of the Maximum Agreement Subtree and Maximum Compatible Tree Problems, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.3, p.289-302, July 2006
	Tobias Riege , Jörg Rothe , Holger Spakowski , Masaki Yamamoto, An improved exact algorithm for the domatic number problem, Information Processing Letters, v.101 n.3, p.101-106, February, 2007
	Vincent Berry , François Nicolas, Maximum agreement and compatible supertrees, Journal of Discrete Algorithms, v.5 n.3, p.564-591, September, 2007