Uriel Feige
Magnús M. Halldórsson
- 1.N. Alon and J. Spencer. The Probabilistic Method. Wiley, 1992.Google Scholar
- 2.S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, June 1991. Google ScholarDigital Library
- 3.J. Beck. An algorithmic approach to the Lov~sz local lemma. Random Structures and Algorithms, 2:343-365, t991. Google ScholarDigital Library
- 4.C. Berge. Balanced matrices. Math. Programming, 2:19-31, 1972.Google ScholarCross Ref
- 5.M. A. Bonucelli. Dominating sets and domatic number of circular arc graphs. Discrete Appl. Math., 12:203- 213, 1985.Google ScholarCross Ref
- 6.E. J. Cockayne and S. T. Hedetniemi. Towards a theory of domination in graphs. Networks, 7:247-261, 1997.Google ScholarCross Ref
- 7.P. Crescenzi nd V. Kann. A compendium of NP optimization problems. http://www, nada. kth. se/theory/problemlist, html, 1999.Google Scholar
- 8.M. Farber. Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl. Math., 7:115-130, 1984.Google ScholarCross Ref
- 9.U. Feige. A threshold of ln n for approximating set cover. J. A CM, 45(2):634-652, 1998. Google ScholarDigital Library
- 10.U. Feige and J. Kilian. Zero knowledge and the chromatic number. J. Comput. Syst. Sci., 57:187-199, Oct. 1998. Google ScholarDigital Library
- 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.Google Scholar
- 12.S. Fujita, M. Yamashita, and T. Kameda. A study on r-configurations- a resource assignment problem on graphs. SIAM J. Disc. Math., 1999. To appear. Google ScholarDigital Library
- 13.M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. Google ScholarDigital Library
- 14.O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proofs. J. A CM, 38(3):691-729, 1991. Google ScholarDigital Library
- 15.T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Domination in Graphs: Advanced Topics. Marcel Dekker, 1998.Google Scholar
- 16.T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, 1998.Google Scholar
- 17.D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. $yst. Sci., 9:256-278, 1974.Google ScholarDigital Library
- 18.H. Kaplan and R. Shamir. The domatic number problem on some perfect graph families. Inf. Process. Left., 49(1):51-56, 1994. Google ScholarDigital Library
- 19.S. Khanna, M. Sudan, and D. Williamson. A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction. In Proc. 29th Annual A CM Symposium on Theory of Computing, 1997. Google ScholarDigital Library
- 20.J. Kratochvfi. Regular codes in regular graphs axe difficult. Discrete Math., 133:191-205, 1994. Google ScholarDigital Library
- 21.L. Lov~sz. On the ratio of optimal integral and fractional covers. Discrete Math., 13:383-390, 1975.Google ScholarDigital Library
- 22.C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. J. A CM, 41(5):960-981, 1994. Google ScholarDigital Library
- 23.F. MacWilliams and N. Sloane. The Theory of Error Correcting Codes. North Holland, 1983.Google Scholar
- 24.M. V. Marathe, H. B. Hunt III, and S. S. Ravi. Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs. Discrete Appl. Math., 64:135-149, 1996. Google ScholarDigital Library
- 25.J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. SiAM J. Comput., 22:838-856, 1993. Google ScholarDigital Library
- 26.M. Naor, L. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In Proc. 36th Ann. IEEE Symp. on Found. of Comp. Sci., pages 182-191, 1995. Google ScholarDigital Library
- 27.A. Paz and S. Moran. Nondeterministic polynomial optimization problems and their approximations. Theoretical Comput. $ci., 15:251-277, 1981.Google Scholar
- 28.S. L. Peng and M. S. Chang. A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, inf. Process. Lett., 43:297-300, 1992. Google ScholarDigital Library
- 29.E. Petrank. The hardness of approximation: Gap location. Comput. Complexity, 4:133-157, 1994. Google ScholarDigital Library
- 30.A. Proskurowski and J. A. Telle. Complexity of graph covering problems. Nordic J. Computing, 5:173-195, 1998. Google ScholarDigital Library
- 31.A. S. Rao and C. P. Rangan. Linear algorithm for domatic number problem on interval graphs. Inf. Process. Left., 33:29-33, 1989. Google ScholarDigital Library
- 32.B. Zelinka. Domatic number and degree of vertices of a graph. Math. Slovaca, 33:145-147, 1983.Google Scholar
Index Terms
- Approximating the domatic number
Recommendations
Computing Roman domatic number of graphs
We show that it is NP -complete to decide whether the Roman domatic number of a given graph is at least three.We then prove an asymptotically optimal threshold of ( log n ) for approximating the Roman domatic number of a graph.Finally, we also determine ...
Graphs with minimum fractional domatic number
AbstractThe domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are ...
The Roman { 2 }-domatic number of graphs
AbstractA Roman { 2 } -dominating function of a graph G with vertex set V ( G ) is defined in Chellali et al. (2016) as a function f : V ( G ) → { 0 , 1 , 2 } having the property that if f ( v ) = 0, then the vertex ...
Comments