2852:
2279:
27:
610:. Figure (c) above shows a dominating set that is a connected dominating set and a total dominating set; the examples in figures (a) and (b) are neither. In contrast to a simple dominating set, a total dominating set may not exist. For example, a graph with one or more vertices and no edges does not have a total dominating set. The
783:
is a set of edges (vertex pairs) whose union is a dominating set; such a set may not exist (for example, a graph with one or more vertices and no edges does not have it). If it exists, then the union of all its edges is a strongly-dominating set. Therefore, the smallest size of an edge-dominating set
986:
then it has no star-dominating sets (since the star of isolated vertices is empty). If G has no isolated vertices, then every dominating set is a star-dominating set and vice versa. The distinction between star-domination and usual domination is more substantial when their fractional variants are
1917:
708:
1938:. This had immediate implications for the dominating set problem, as there are straightforward vertex to set and edge to non-disjoint-intersection bijections between the two problems. This proved the dominating set problem to be
1673:
board, and two such vertices are connected if and only if they intersect. The only independent sets are sets of only rows or sets of only columns, and each of them can be dominated by a single vertex (a column or a row), so
461:
1789:
3324:
of the kernel. More generally, the dominating set problem and many variants of the problem are fixed-parameter tractable when parameterized by both the size of the dominating set and the size of the smallest
30:
Three dominating sets of the same graph (in red). The domination number of this graph is 2: (b) and (c) show that there is a dominating set with 2 vertices, and there is no dominating set with only 1 vertex.
1061:
A dominating set may or may not be an independent set. For example, figures (a) and (b) above show independent dominating sets, while figure (c) illustrates a dominating set that is not an independent set.
1241:
1794:
774:
1970:) show that an efficient algorithm for the minimum dominating set problem would provide an efficient algorithm for the set cover problem, and vice versa. Moreover, the reductions preserve the
3162:
1393:
841:
3942:
Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications",
383:
251:
3299:
On the other hand, if the input graph is planar, the problem remains NP-hard, but a fixed-parameter algorithm is known. In fact, the problem has a kernel of size linear in
215:
505:
form a connected dominating set. Therefore, finding minimum connected dominating sets is equivalent to finding spanning trees with the maximum possible number of leaves.
608:
315:
570:
544:
277:
623:
347:
1083:
is the size of the smallest dominating set that is an independent set. Equivalently, it is the size of the smallest maximal independent set. The minimum in
4317:
van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), "Inclusion/Exclusion Meets
Measure and Conquer: Exact Algorithms for Counting Dominating Sets",
1926:
The domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s. In 1972,
3823:
SOFSEM 2006: 32nd
Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 21-27, 2006, Proceedings
2267:. Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa. In particular, an efficient
4526:
398:
4286:
Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in
Epstein, Leah; Ferragina, Paolo (eds.),
3247:, who also show that the number of minimum dominating sets can be computed in this time. The number of minimal dominating sets is at most
4211:; Safra, S. (1997), "A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP",
3911:
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms",
4079:
Hedetniemi, S. T.; Laskar, R. C. (1990), "Bibliography on domination in graphs and some basic definitions of domination parameters",
1912:{\displaystyle {\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}}
1481:. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect.
1156:
4334:
4307:
4020:
3838:
996:
is a partition of the vertices into disjoint dominating sets. The domatic number is the maximum size of a domatic partition.
4137:
Klasing, Ralf; Laforest, Christian (2004), "Hardness results and approximation algorithms of k-tuple domination in graphs",
2003:
approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than
3971:
Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Dominating sets in planar graphs: branch-width and exponential speed-up",
3180:
1993:, and finding a sublogarithmic approximation factor is NP-hard. More specifically, the greedy algorithm provides a factor
3270:
plays a central role in the theory of parameterized complexity. It is the most well-known problem complete for the class
1989:
The approximability of set covering is also well understood: a logarithmic approximation factor can be found by using a
713:
4476:
4446:
4291:
4231:
4052:
1955:
4214:
3326:
3109:
1029:
is also a dominating set and this process can be repeated over any infinite sequence of choices of vertices
124:
4158:
Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Optimization, Approximation, and
Complexity Classes",
520:
the vertices in the dominating set themselves, have a neighbor in the dominating set. That is: for every vertex
4128:
4081:
3509:
Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs".
2596:
1340:
1042:
156:, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in
4288:
Algorithms – ESA 2012: 20th Annual
European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings
4521:
4516:
4114:
4494:
4039:
787:
43:
3356:
3274:
and used in many reductions to show intractability of other problems. In particular, the problem is not
3106:
be the cardinality of dominating set obtained using greedy approximation then following relation holds,
4178:
Parekh, Abhay K. (1991), "Analysis of a greedy heuristic for finding small dominating sets in graphs",
356:
224:
3764:
Allan, Robert B.; Laskar, Renu (1978), "On domination and independent domination numbers of a graph",
1990:
4253:; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs",
4044:
3275:
3192:
1608:. Dominating subsets of vertices requires potentially less vertices than dominating all vertices, so
128:
4365:
3849:
3329:
1563:
478:
473:
20:
3172:
is number of edges in given undirected graph. For fixed Δ, this qualifies as a dominating set for
2043:: given an instance of one problem, we can construct an equivalent instance of the other problem.
1397:
is a smallest dominating set that is also independent (it is a smallest maximal independent set).
194:
1971:
1536:
1046:
146:
575:
282:
4360:
3807:
3352:
2090:
1001:
157:
4383:
2588:
703:{\displaystyle \gamma ^{strong}(G):=\min\{|D|:D{\text{ is a strongly-dominating set of }}G\}}
905:-dominating set (for example, the set of all vertices); but only graphs with minimum degree
549:
523:
256:
4062:
4000:
Förster, Klaus-Tycho. (2013), "Approximating Fault-Tolerant
Domination in General Graphs",
3903:
3792:
3321:
1416:, that is, every minimum maximal independent set is a minimum dominating set. For example,
3796:
1049:, so any maximal independent set in a graph is necessarily also a minimal dominating set.
864:; such a set always exists (for example, the set of all edges is an edge-dominating set).
323:
8:
3815:
3811:
3333:
3317:
1555:
967:
847:
153:
4435:
4418:
4274:
4255:
4237:
3988:
3959:
3930:
3913:
3752:
3734:
3725:
3534:
3894:
3459:
3442:
501:
is any spanning tree in a graph with more than two vertices, the non-leaf vertices of
4482:
4472:
4452:
4442:
4330:
4303:
4227:
4191:
4171:
4122:
4105:
4095:
4066:
4048:
4016:
3834:
3778:
3526:
3464:
3362:
2036:
1963:
1931:
992:
878:
neighbors in the set (a standard dominating set is a 1-dominating set). Similarly, a
4278:
4241:
3538:
3092:
If the graph has maximum degree Δ, then the greedy approximation algorithm finds an
1983:
4464:
4430:
4422:
4408:
4400:
4370:
4322:
4295:
4264:
4219:
4195:
4187:
4167:
4146:
4090:
4034:
4008:
4003:
3992:
3980:
3963:
3951:
3934:
3922:
3889:
3864:
3826:
3773:
3744:
3720:
3518:
3454:
1471:
120:
3756:
2035:
The following two reductions show that the minimum dominating set problem and the
4326:
4321:, Lecture Notes in Computer Science, vol. 5757, Springer, pp. 554–565,
4299:
4250:
4058:
3899:
3825:, Lecture Notes in Computer Science, vol. 3831, Springer, pp. 237–245,
3788:
3716:
3184:
1437:
983:
161:
1685:. However, to dominate all vertices we need at least one row and one column, so
3367:
4374:
4150:
4012:
3984:
3869:
3522:
1982:
algorithm for the set cover problem and vice versa. Both problems are in fact
889:
neighbors in the set (a total dominating set is a 1-tuple dominating set). An
4510:
4070:
4030:
3877:
3620:
3530:
3468:
486:
4486:
4456:
3955:
3926:
3880:; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey",
901:-tuple dominating set can be found in polynomial time. Every graph admits a
4391:
4351:
Grandoni, F. (2006), "A note on the complexity of minimum dominating set",
3188:
2851:
1927:
1094:
is taken over less elements (only the independent sets are considered), so
456:{\displaystyle \gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}}
35:
4269:
4223:
3748:
4043:. Series of Books in the Mathematical Sciences (1st ed.). New York:
3336:, a very general class of sparse graphs that includes the planar graphs.
2580:
2040:
1959:
1939:
1935:
117:
3830:
3644:
2292:
shown on the right, we construct a set cover instance with the universe
16:
Subset of a graph's nodes such that all other nodes link to at least one
4404:
4200:
4002:
Proc. of the Tenth
Workshop on Analytic Algorithmics and Combinatorics
3372:
3340:
1489:
874:
is a set of vertices such that each vertex not in the set has at least
4113:. PhD thesis, Department of Numerical Analysis and Computing Science,
4040:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
1978:
algorithm for minimum dominating sets would provide a polynomial-time
1045:: an independent set is also a dominating set if and only if it is a
885:
is a set of vertices such that each vertex in the graph has at least
385:. A more interesting challenge is to find small dominating sets. The
4413:
3692:
3632:
3816:"Nonblocker: Parameterized algorithmics for minimum dominating set"
3739:
3656:
3608:
2278:
149:, as well as efficient exact algorithms for certain graph classes.
4208:
3786:
3626:
3487:
2024:
1951:
26:
2626:
is a feasible solution of the set cover problem for some subset
1665:
be a graph in which the vertices are the rows and columns of an
948:
497:
forms the set of non-leaf vertices of the tree; conversely, if
188:
152:
Dominating sets are of practical interest in several areas. In
3723:(2004), "Polynomial-time data reduction for dominating set",
1502:
is claw-free, and hence a minimum maximal independent set in
4319:
Proc. 17th Annual
European Symposium on Algorithms, ESA 2009
3941:
3650:
3572:
3343:, can be found by a fixed-parameter algorithm on any graph.
516:) is a set of vertices such that all vertices in the graph,
4107:
3545:
3271:
1236:{\displaystyle x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}}
86:
is the number of vertices in a smallest dominating set for
3680:
3562:
3560:
3410:
3398:
3191:. A minimum dominating set can be found in linear time in
2744:. Then it is possible to construct another dominating set
2444:
be an instance of the set cover problem with the universe
1954:
problem – the decision version of set covering was one of
1945:
1715:
can be arbitrarily large. For example, if the vertices of
4316:
3668:
3244:
3173:
940:-dominating set can be found in polynomial time as well.
916:-tuple dominating set. However, even if the graph admits
4384:"Approximation algorithms for connected dominating sets"
4248:
3805:
3787:
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús;
3698:
3638:
2861:
The illustration on the right show the construction for
4463:
4429:
4157:
3714:
3662:
3614:
3557:
3386:
3002:
is a set cover; this corresponds to the dominating set
3876:
3493:
3475:
3099:-approximation of a minimum dominating set. Also, let
2826:
is a feasible solution of the set cover problem, with
2427:
2224:
is a feasible solution of the set cover problem, then
2184:
is a feasible solution of the set cover problem, with
2046:
3112:
1792:
1343:
1159:
1005:
is a dynamic version of domination in which a vertex
790:
716:
626:
578:
552:
526:
401:
359:
326:
285:
259:
227:
197:
3910:
3584:
3219:
1566:
has the same size as a minimum edge dominating set.
1962:between the minimum dominating set problem and the
4434:
3850:"Completeness in approximation classes beyond APX"
3596:
3422:
3296:exists unless the W-hierarchy collapses to FPT=W.
3222:show how to find a minimum dominating set in time
3156:
1911:
1387:
1235:
1036:
835:
769:{\displaystyle \gamma ^{strong}(G)\geq \gamma (G)}
768:
702:
602:
564:
538:
455:
377:
341:
309:
271:
245:
209:
3806:Dehne, Frank; Fellows, Michael; Fernau, Henning;
3278:in the sense that no algorithm with running time
2271:algorithm for set covering provides an efficient
1569:
1052:
4508:
4078:
3848:Escoffier, Bruno; Paschos, Vangelis Th. (2006),
3847:
3578:
3551:
3508:
3236:and polynomial space. A faster algorithm, using
1634:The inequality can be strict - there are graphs
1120:The inequality can be strict - there are graphs
664:
417:
320:Every graph has at least one dominating set: if
127:. Therefore it is believed that there may be no
4136:
3416:
2251:Hence the size of a minimum dominating set for
4467:; Hedetniemi, Stephen; Slater, Peter (1998b),
4433:; Hedetniemi, Stephen; Slater, Peter (1998a),
4294:, vol. 7501, Springer, pp. 802–812,
4285:
3686:
485:is a connected dominating set, one can form a
353:is a dominating set, since there is no vertex
3970:
3674:
3339:The complementary set to a dominating set, a
1782:. The following relations hold for any graph
1778:, of the smallest independent set dominating
4029:
3392:
3303:, and running times that are exponential in
3157:{\displaystyle d_{g}\leq N+1-{\sqrt {2M+1}}}
1382:
1344:
697:
667:
450:
420:
349:the set of all vertices, then by definition
4381:
3763:
3481:
3261:
2255:equals the size of a minimum set cover for
691: is a strongly-dominating set of
1770:is the maximum, over all independent sets
1596:is the maximum, over all independent sets
19:For Dominator in control flow graphs, see
4412:
4364:
4268:
4199:
4094:
3893:
3868:
3777:
3738:
3458:
3447:Journal of Combinatorial Theory, Series A
3251:and all such sets can be listed in time
3245:van Rooij, Nederlof & van Dijk (2009)
3176:membership; in fact, it is APX-complete.
1388:{\displaystyle \{x_{1},\ldots ,x_{p},b\}}
57:of its vertices, such that any vertex of
4350:
4207:
3798:A Compendium of NP Optimization Problems
3639:Takamizawa, Nishizeki & Saito (1982)
3590:
3440:
3359:to the domination number of its factors.
3027:is another dominating set for the graph
1958:. There exist a pair of polynomial-time
978:) intersects the star of some vertex in
25:
4160:Journal of Computer and System Sciences
3999:
3663:Alber, Fellows & Niedermeier (2004)
3428:
2275:algorithm for minimum dominating sets.
1946:Algorithms and computational complexity
1041:Dominating sets are closely related to
1013:is chosen and replaced with a neighbor
932:-dominating set for the same graph; An
4527:Computational problems in graph theory
4509:
4177:
3602:
3494:Faudree, Flandrin & Ryjáček (1997)
1950:The set cover problem is a well-known
856:of edges, such that every edge not in
160:, and in designing secure systems for
4469:Domination in Graphs: Advanced Topics
3615:Papadimitriou & Yannakakis (1991)
3375:- the complement of a dominating set.
3355:- relates the domination number of a
1719:are all the subsets of squares of an
836:{\displaystyle \gamma ^{strong}(G)/2}
4493:
4437:Fundamentals of Domination in Graphs
4103:
3566:
3504:
3502:
3404:
3220:Fomin, Grandoni & Kratsch (2009)
3181:polynomial-time approximation scheme
3035:, we can construct a dominating set
2366:– this corresponds to the set cover
1513:is also a minimum dominating set in
924:-tuple dominating set can be nearly
860:is adjacent to at least one edge in
167:
3229:and exponential space, and in time
3207:-vertex graph can be found in time
3198:
2495:as follows: the set of vertices is
2428:From set covering to dominating set
2047:From dominating set to set covering
13:
4344:
3795:(2000), "Minimum dominating set",
3218:by inspecting all vertex subsets.
2850:
2277:
1400:There are graph families in which
1310:is a smallest dominating set. If
444: is a dominating set of
14:
4538:
4292:Lecture Notes in Computer Science
3499:
3443:"Domination numbers and homology"
3434:
3332:; that is, the problem is FPT on
3266:Finding a dominating set of size
3183:(PTAS) for special cases such as
1967:
1657:. For example, for some integer
1604:, of the smallest set dominating
920:-tuple dominating set, a minimum
477:is a dominating set that is also
378:{\displaystyle u\in V\setminus D}
369:
246:{\displaystyle u\in V\setminus D}
237:
4215:Symposium on Theory of Computing
3087:
2480:are disjoint. Construct a graph
1754:bi-independent domination number
4501:(2 ed.), Pearson Education
3203:A minimum dominating set of an
2100:, and the family of subsets is
2077:construct a set cover instance
2030:
1974:: for any α, a polynomial-time
1696:. Moreover, the ratio between
1037:Dominating and independent sets
145:. However, there are efficient
125:computational complexity theory
4382:Guha, S.; Khuller, S. (1998),
4353:Journal of Discrete Algorithms
4180:Information Processing Letters
4139:Information Processing Letters
3944:ACM Transactions on Algorithms
3579:Escoffier & Paschos (2006)
3552:Hedetniemi & Laskar (1990)
1956:Karp's 21 NP-complete problems
1902:
1896:
1884:
1878:
1859:
1853:
1843:
1837:
1825:
1819:
1806:
1800:
1580:independence domination number
974:(the set of edges adjacent to
822:
816:
763:
757:
748:
742:
679:
671:
658:
652:
591:
579:
432:
424:
411:
405:
298:
286:
1:
4115:Royal Institute of Technology
3895:10.1016/S0012-365X(96)00045-3
3708:
3460:10.1016/S0097-3165(03)00045-1
3417:Klasing & Laforest (2004)
3054:corresponds to the set cover
2288:For example, given the graph
2141:and all vertices adjacent to
1260:are defined as follows: each
1067:independent domination number
4499:Introduction to Graph Theory
4327:10.1007/978-3-642-04128-0_50
4300:10.1007/978-3-642-33090-2_69
4192:10.1016/0020-0190(91)90021-9
4172:10.1016/0022-0000(91)90023-X
4096:10.1016/0012-365X(90)90365-O
3857:Theoretical Computer Science
3779:10.1016/0012-365X(78)90105-X
3687:Telle & Villanger (2012)
3441:Meshulam, Roy (2003-05-01).
3316:may be obtained by applying
2538:, and there is also an edge
958:such that, for every vertex
936:-approximation of a minimum
928:times as large as a minimum
897:-approximation of a minimum
210:{\displaystyle D\subseteq V}
7:
4075:, p. 190, problem GT2.
3675:Fomin & Thilikos (2006)
3357:cartesian product of graphs
3346:
3330:complete bipartite subgraph
2729:is adjacent to a vertex in
2394:is dominated by the vertex
466:
10:
4543:
4127:: CS1 maint: postscript (
3393:Garey & Johnson (1979)
2448:and the family of subsets
1921:
1543:, and a dominating set in
603:{\displaystyle (u,v)\in E}
310:{\displaystyle (u,v)\in E}
172:Given an undirected graph
18:
4375:10.1016/j.jda.2005.03.002
4218:, ACM, pp. 475–484,
4151:10.1016/j.ipl.2003.10.004
4045:W. H. Freeman and Company
4013:10.1137/1.9781611973037.4
3985:10.1137/S0097539702419649
3973:SIAM Journal on Computing
3870:10.1016/j.tcs.2006.05.023
3523:10.1007/s00493-007-2086-y
3482:Allan & Laskar (1978)
3276:fixed-parameter tractable
3046:and which is a subset of
3042:which is not larger than
1025:) such that the modified
97:concerns testing whether
4007:, SIAM, pp. 25–32,
3379:
3262:Parameterized complexity
2740:be a dominating set for
2640:is a dominating set for
2408:is contained in the set
2387:For example, the vertex
2362:is a dominating set for
2228:is a dominating set for
2156:is a dominating set for
1564:minimum maximal matching
1524:. An independent set in
1449:domination-perfect graph
612:strong domination number
474:connected dominating set
147:approximation algorithms
21:Dominator (graph theory)
3956:10.1145/1435375.1435384
3927:10.1145/1552285.1552286
3627:Crescenzi et al. (2000)
3168:is number of nodes and
2719:must be nonempty, each
2695:, and by construction,
2137:consists of the vertex
1991:simple greedy algorithm
1151:consisting of vertices
1047:maximal independent set
514:strongly-dominating set
69:, or has a neighbor in
4213:Proc. 29th Annual ACM
3591:Raz & Safra (1997)
3193:series–parallel graphs
3158:
2855:
2774:: simply replace each
2282:
1913:
1389:
1237:
1002:eternal dominating set
837:
770:
704:
604:
566:
565:{\displaystyle v\in D}
540:
539:{\displaystyle u\in V}
457:
379:
343:
311:
273:
272:{\displaystyle v\in D}
247:
211:
158:document summarization
95:dominating set problem
31:
4270:10.1145/322326.322328
4224:10.1145/258533.258641
3749:10.1145/990308.990309
3179:The problem admits a
3159:
3050:. The dominating set
2854:
2281:
2039:are equivalent under
1914:
1390:
1238:
883:-tuple dominating set
838:
771:
705:
605:
567:
541:
458:
380:
344:
312:
274:
248:
212:
29:
4522:NP-complete problems
4517:Graph theory objects
4104:Kann, Viggo (1992),
4082:Discrete Mathematics
3882:Discrete Mathematics
3766:Discrete Mathematics
3334:biclique-free graphs
3322:branch-decomposition
3110:
1966:. These reductions (
1790:
1341:
1283:is adjacent to each
1157:
1143:. For example, let
982:. Clearly, if G has
891:(1 + log
788:
714:
624:
576:
550:
546:, there is a vertex
524:
510:total dominating set
399:
357:
342:{\displaystyle D=V=}
324:
283:
257:
253:, there is a vertex
225:
221:if for every vertex
195:
116:; it is a classical
3831:10.1007/11611257_21
3699:Dehne et al. (2006)
3651:Fomin et al. (2008)
3569:, pp. 108–109.
3353:Vizing's conjecture
3318:dynamic programming
2509:, there is an edge
1972:approximation ratio
1556:edge dominating set
945:star-dominating set
849:edge-dominating set
781:dominating edge-set
154:wireless networking
129:efficient algorithm
4405:10.1007/PL00009201
4256:Journal of the ACM
3914:Journal of the ACM
3793:Woeginger, Gerhard
3726:Journal of the ACM
3717:Fellows, Michael R
3243:time was found by
3154:
2856:
2660:: First, for each
2524:between each pair
2476:and the index set
2401:, and the element
2283:
1909:
1907:
1727:board, then still
1554:corresponds to an
1385:
1233:
1009:in dominating set
833:
766:
700:
600:
562:
536:
453:
375:
339:
307:
269:
243:
207:
108:for a given graph
32:
4471:, Marcel Dekker,
4465:Haynes, Teresa W.
4441:, Marcel Dekker,
4431:Haynes, Teresa W.
4336:978-3-642-04127-3
4309:978-3-642-33089-6
4035:Johnson, David S.
4031:Garey, Michael R.
4022:978-1-61197-254-2
3840:978-3-540-31198-0
3812:Rosamond, Frances
3721:Niedermeier, Rolf
3363:Set cover problem
3292:for any function
3152:
2981:In this example,
2355:In this example,
2200:. Conversely, if
2037:set cover problem
1964:set cover problem
1932:set cover problem
1535:corresponds to a
1149:double star graph
993:domatic partition
984:isolated vertices
692:
445:
387:domination number
168:Formal definition
131:that can compute
77:domination number
4534:
4502:
4495:West, Douglas B.
4489:
4459:
4440:
4425:
4416:
4388:
4377:
4368:
4339:
4312:
4281:
4272:
4249:Takamizawa, K.;
4244:
4204:
4203:
4174:
4153:
4132:
4126:
4118:
4112:
4099:
4098:
4089:(1–3): 257–277,
4074:
4025:
3995:
3966:
3937:
3906:
3897:
3873:
3872:
3863:(1–3): 369–377,
3854:
3843:
3820:
3801:
3789:Karpinski, Marek
3782:
3781:
3759:
3742:
3702:
3696:
3690:
3684:
3678:
3672:
3666:
3660:
3654:
3648:
3642:
3636:
3630:
3624:
3618:
3612:
3606:
3600:
3594:
3588:
3582:
3576:
3570:
3564:
3555:
3549:
3543:
3542:
3506:
3497:
3491:
3485:
3479:
3473:
3472:
3462:
3438:
3432:
3426:
3420:
3414:
3408:
3402:
3396:
3390:
3315:
3311:
3310:
3302:
3295:
3291:
3269:
3257:
3250:
3242:
3235:
3228:
3217:
3206:
3199:Exact algorithms
3185:unit disk graphs
3171:
3167:
3163:
3161:
3160:
3155:
3153:
3139:
3122:
3121:
3105:
3098:
3081:
3053:
3049:
3045:
3041:
3034:
3030:
3026:
3008:
3001:
2972:
2950:
2929:
2912:
2891:
2847:
2845:
2839:
2833:
2825:
2801:
2797:
2787:
2773:
2763:
2761:
2755:
2747:
2743:
2739:
2736:Conversely, let
2732:
2728:
2718:
2715:. Second, since
2714:
2711:is dominated by
2710:
2706:
2703:are adjacent in
2702:
2698:
2694:
2679:
2669:
2659:
2657:
2651:
2643:
2639:
2635:
2625:
2594:
2586:
2578:
2574:
2559:
2549:
2537:
2523:
2508:
2494:
2479:
2475:
2471:
2447:
2443:
2420:
2407:
2400:
2393:
2386:
2365:
2361:
2354:
2344:
2335:
2326:
2317:
2308:
2299:and the subsets
2298:
2297:= {1, 2, ..., 6}
2291:
2274:
2270:
2266:
2254:
2247:
2245:
2239:
2231:
2227:
2223:
2199:
2197:
2191:
2183:
2159:
2155:
2148:
2144:
2140:
2136:
2129:
2099:
2095:
2089:as follows: the
2088:
2076:
2065:
2022:
2015:
2013:
2002:
2000:
1984:Log-APX-complete
1981:
1977:
1918:
1916:
1915:
1910:
1908:
1785:
1781:
1777:
1773:
1769:
1765:
1748:
1737:
1726:
1722:
1718:
1714:
1695:
1684:
1672:
1668:
1664:
1660:
1656:
1637:
1630:
1626:
1607:
1603:
1599:
1595:
1591:
1574:independent sets
1561:
1553:
1542:
1534:
1523:
1512:
1501:
1487:
1480:
1476:
1472:induced subgraph
1469:
1446:
1435:
1431:
1415:
1396:
1394:
1392:
1391:
1386:
1375:
1374:
1356:
1355:
1334:
1319:
1309:
1297:
1289:
1282:
1278:
1274:
1270:
1266:
1259:
1256:. The edges of
1255:
1244:
1242:
1240:
1239:
1234:
1232:
1231:
1213:
1212:
1188:
1187:
1169:
1168:
1146:
1142:
1123:
1116:
1112:
1093:
1082:
1078:
1057:independent sets
1043:independent sets
935:
911:
896:
846:In contrast, an
842:
840:
839:
834:
829:
815:
814:
775:
773:
772:
767:
741:
740:
709:
707:
706:
701:
693:
690:
682:
674:
651:
650:
620:is defined as:
619:
609:
607:
606:
601:
571:
569:
568:
563:
545:
543:
542:
537:
462:
460:
459:
454:
446:
443:
435:
427:
395:is defined as:
394:
384:
382:
381:
376:
348:
346:
345:
340:
316:
314:
313:
308:
278:
276:
275:
270:
252:
250:
249:
244:
216:
214:
213:
208:
186:
162:electrical grids
144:
138:
121:decision problem
115:
111:
107:
89:
85:
74:
68:
62:
56:
50:
4542:
4541:
4537:
4536:
4535:
4533:
4532:
4531:
4507:
4506:
4479:
4449:
4386:
4366:10.1.1.108.3223
4347:
4345:Further reading
4337:
4310:
4234:
4120:
4119:
4110:
4055:
4023:
3888:(1–3): 87–147,
3852:
3841:
3818:
3715:Alber, Jochen;
3711:
3706:
3705:
3697:
3693:
3685:
3681:
3673:
3669:
3661:
3657:
3649:
3645:
3637:
3633:
3625:
3621:
3613:
3609:
3601:
3597:
3589:
3585:
3577:
3573:
3565:
3558:
3550:
3546:
3507:
3500:
3492:
3488:
3480:
3476:
3439:
3435:
3427:
3423:
3415:
3411:
3403:
3399:
3391:
3387:
3382:
3349:
3313:
3306:
3304:
3300:
3293:
3279:
3267:
3264:
3252:
3248:
3237:
3230:
3223:
3208:
3204:
3201:
3169:
3165:
3138:
3117:
3113:
3111:
3108:
3107:
3104:
3100:
3093:
3090:
3079:
3072:
3065:
3055:
3051:
3047:
3043:
3036:
3032:
3028:
3017:
3003:
2999:
2992:
2982:
2958:
2952:
2936:
2930:
2919:
2913:
2898:
2892:
2890:= {1, 2, 3, 4},
2862:
2841:
2840:| ≤ |
2835:
2834:| = |
2829:
2827:
2815:
2803:
2799:
2789:
2788:by a neighbour
2775:
2765:
2757:
2756:| ≤ |
2751:
2749:
2745:
2741:
2737:
2730:
2720:
2716:
2712:
2708:
2704:
2700:
2696:
2693:
2681:
2671:
2661:
2653:
2652:| = |
2647:
2645:
2641:
2637:
2627:
2615:
2603:
2597:independent set
2592:
2584:
2576:
2573:
2561:
2551:
2539:
2525:
2510:
2496:
2481:
2477:
2473:
2472:we assume that
2461:
2449:
2445:
2433:
2430:
2415:
2409:
2402:
2395:
2388:
2384:
2377:
2367:
2363:
2356:
2352:
2346:
2343:= {1, 2, 5, 6},
2342:
2336:
2333:
2327:
2325:= {2, 3, 4, 6},
2324:
2318:
2316:= {1, 2, 3, 5},
2315:
2309:
2306:
2300:
2293:
2289:
2273:α-approximation
2272:
2269:α-approximation
2268:
2256:
2252:
2241:
2240:| = |
2235:
2233:
2229:
2225:
2213:
2201:
2193:
2192:| = |
2187:
2185:
2173:
2161:
2157:
2153:
2146:
2142:
2138:
2135:
2131:
2127:
2118:
2111:
2101:
2097:
2093:
2078:
2067:
2052:
2049:
2033:
2017:
2009:
2004:
1996:
1994:
1980:α-approximation
1979:
1976:α-approximation
1975:
1948:
1924:
1906:
1905:
1862:
1847:
1846:
1809:
1793:
1791:
1788:
1787:
1783:
1779:
1775:
1771:
1767:
1756:
1739:
1728:
1724:
1720:
1716:
1697:
1686:
1675:
1670:
1666:
1662:
1658:
1639:
1635:
1628:
1627:for all graphs
1609:
1605:
1601:
1597:
1593:
1582:
1576:
1559:
1544:
1540:
1525:
1514:
1503:
1492:
1485:
1478:
1474:
1452:
1444:
1438:claw-free graph
1433:
1417:
1401:
1370:
1366:
1351:
1347:
1342:
1339:
1338:
1336:
1321:
1311:
1299:
1291:
1288:
1284:
1280:
1276:
1275:is adjacent to
1272:
1268:
1267:is adjacent to
1265:
1261:
1257:
1246:
1227:
1223:
1208:
1204:
1183:
1179:
1164:
1160:
1158:
1155:
1154:
1152:
1144:
1125:
1121:
1114:
1113:for all graphs
1095:
1084:
1080:
1069:
1059:
1039:
933:
906:
890:
872:-dominating set
825:
795:
791:
789:
786:
785:
721:
717:
715:
712:
711:
689:
678:
670:
631:
627:
625:
622:
621:
615:
577:
574:
573:
551:
548:
547:
525:
522:
521:
469:
442:
431:
423:
400:
397:
396:
390:
358:
355:
354:
325:
322:
321:
284:
281:
280:
258:
255:
254:
226:
223:
222:
196:
193:
192:
173:
170:
140:
139:for all graphs
132:
113:
109:
98:
87:
79:
70:
64:
58:
52:
46:
24:
17:
12:
11:
5:
4540:
4530:
4529:
4524:
4519:
4505:
4504:
4491:
4477:
4461:
4447:
4427:
4399:(4): 374–387,
4379:
4359:(2): 209–214,
4346:
4343:
4342:
4341:
4335:
4314:
4308:
4283:
4263:(3): 623–641,
4246:
4232:
4205:
4186:(5): 237–240,
4175:
4166:(3): 425–440,
4155:
4134:
4101:
4076:
4053:
4027:
4021:
3997:
3968:
3939:
3921:(5): 25:1–32,
3908:
3878:Faudree, Ralph
3874:
3845:
3839:
3803:
3784:
3761:
3733:(3): 363–384,
3710:
3707:
3704:
3703:
3691:
3679:
3667:
3655:
3643:
3631:
3619:
3607:
3595:
3583:
3571:
3556:
3544:
3517:(3): 253–267.
3498:
3486:
3474:
3453:(2): 321–330.
3433:
3429:Förster (2013)
3421:
3409:
3407:, Section 3.1.
3397:
3384:
3383:
3381:
3378:
3377:
3376:
3370:
3368:Bondage number
3365:
3360:
3348:
3345:
3263:
3260:
3200:
3197:
3151:
3148:
3145:
3142:
3137:
3134:
3131:
3128:
3125:
3120:
3116:
3102:
3089:
3086:
3085:
3084:
3083:
3082:
3077:
3070:
3063:
3012:
3011:
3010:
3009:
2997:
2990:
2976:
2975:
2974:
2973:
2956:
2934:
2917:
2896:
2811:
2689:
2611:
2569:
2457:
2429:
2426:
2425:
2424:
2423:
2422:
2413:
2382:
2375:
2350:
2340:
2331:
2322:
2313:
2304:
2209:
2169:
2133:
2123:
2116:
2109:
2071:= {1, 2, ...,
2051:Given a graph
2048:
2045:
2032:
2029:
1947:
1944:
1923:
1920:
1904:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1863:
1861:
1858:
1855:
1852:
1849:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1810:
1808:
1805:
1802:
1799:
1796:
1795:
1575:
1568:
1562:. Therefore a
1484:For any graph
1384:
1381:
1378:
1373:
1369:
1365:
1362:
1359:
1354:
1350:
1346:
1286:
1263:
1230:
1226:
1222:
1219:
1216:
1211:
1207:
1203:
1200:
1197:
1194:
1191:
1186:
1182:
1178:
1175:
1172:
1167:
1163:
1058:
1051:
1038:
1035:
832:
828:
824:
821:
818:
813:
810:
807:
804:
801:
798:
794:
765:
762:
759:
756:
753:
750:
747:
744:
739:
736:
733:
730:
727:
724:
720:
699:
696:
688:
685:
681:
677:
673:
669:
666:
663:
660:
657:
654:
649:
646:
643:
640:
637:
634:
630:
599:
596:
593:
590:
587:
584:
581:
561:
558:
555:
535:
532:
529:
468:
465:
452:
449:
441:
438:
434:
430:
426:
422:
419:
416:
413:
410:
407:
404:
374:
371:
368:
365:
362:
338:
335:
332:
329:
306:
303:
300:
297:
294:
291:
288:
268:
265:
262:
242:
239:
236:
233:
230:
219:dominating set
206:
203:
200:
169:
166:
40:dominating set
15:
9:
6:
4:
3:
2:
4539:
4528:
4525:
4523:
4520:
4518:
4515:
4514:
4512:
4500:
4496:
4492:
4488:
4484:
4480:
4478:0-8247-0034-1
4474:
4470:
4466:
4462:
4458:
4454:
4450:
4448:0-8247-0033-3
4444:
4439:
4438:
4432:
4428:
4424:
4420:
4415:
4410:
4406:
4402:
4398:
4394:
4393:
4385:
4380:
4376:
4372:
4367:
4362:
4358:
4354:
4349:
4348:
4338:
4332:
4328:
4324:
4320:
4315:
4311:
4305:
4301:
4297:
4293:
4289:
4284:
4280:
4276:
4271:
4266:
4262:
4258:
4257:
4252:
4251:Nishizeki, T.
4247:
4243:
4239:
4235:
4233:0-89791-888-6
4229:
4225:
4221:
4217:
4216:
4210:
4206:
4202:
4197:
4193:
4189:
4185:
4181:
4176:
4173:
4169:
4165:
4161:
4156:
4152:
4148:
4144:
4140:
4135:
4130:
4124:
4116:
4109:
4108:
4102:
4097:
4092:
4088:
4084:
4083:
4077:
4072:
4068:
4064:
4060:
4056:
4054:9780716710455
4050:
4046:
4042:
4041:
4036:
4032:
4028:
4024:
4018:
4014:
4010:
4006:
4005:
3998:
3994:
3990:
3986:
3982:
3978:
3974:
3969:
3965:
3961:
3957:
3953:
3950:(1): 9:1–17,
3949:
3945:
3940:
3936:
3932:
3928:
3924:
3920:
3916:
3915:
3909:
3905:
3901:
3896:
3891:
3887:
3883:
3879:
3875:
3871:
3866:
3862:
3858:
3851:
3846:
3842:
3836:
3832:
3828:
3824:
3817:
3813:
3809:
3808:Prieto, Elena
3804:
3800:
3799:
3794:
3790:
3785:
3780:
3775:
3771:
3767:
3762:
3758:
3754:
3750:
3746:
3741:
3736:
3732:
3728:
3727:
3722:
3718:
3713:
3712:
3700:
3695:
3688:
3683:
3676:
3671:
3664:
3659:
3652:
3647:
3640:
3635:
3628:
3623:
3616:
3611:
3604:
3603:Parekh (1991)
3599:
3592:
3587:
3580:
3575:
3568:
3563:
3561:
3553:
3548:
3540:
3536:
3532:
3528:
3524:
3520:
3516:
3512:
3511:Combinatorica
3505:
3503:
3495:
3490:
3483:
3478:
3470:
3466:
3461:
3456:
3452:
3448:
3444:
3437:
3430:
3425:
3418:
3413:
3406:
3401:
3394:
3389:
3385:
3374:
3371:
3369:
3366:
3364:
3361:
3358:
3354:
3351:
3350:
3344:
3342:
3337:
3335:
3331:
3328:
3323:
3319:
3312:and cubic in
3309:
3297:
3290:
3286:
3282:
3277:
3273:
3259:
3255:
3246:
3240:
3233:
3226:
3221:
3215:
3211:
3196:
3194:
3190:
3189:planar graphs
3186:
3182:
3177:
3175:
3149:
3146:
3143:
3140:
3135:
3132:
3129:
3126:
3123:
3118:
3114:
3096:
3088:Special cases
3076:
3069:
3062:
3058:
3039:
3024:
3020:
3016:
3015:
3014:
3013:
3006:
2996:
2989:
2985:
2980:
2979:
2978:
2977:
2970:
2966:
2962:
2955:
2948:
2944:
2940:
2933:
2927:
2923:
2916:
2910:
2906:
2902:
2895:
2889:
2885:
2881:
2877:
2873:
2869:
2865:
2860:
2859:
2858:
2857:
2853:
2849:
2844:
2838:
2832:
2823:
2819:
2814:
2810:
2806:
2796:
2792:
2786:
2782:
2778:
2772:
2768:
2760:
2754:
2734:
2727:
2723:
2692:
2688:
2684:
2678:
2674:
2668:
2664:
2656:
2650:
2634:
2630:
2623:
2619:
2614:
2610:
2606:
2600:
2598:
2590:
2582:
2572:
2568:
2564:
2558:
2554:
2547:
2543:
2536:
2532:
2528:
2522:
2518:
2514:
2507:
2503:
2499:
2492:
2488:
2484:
2469:
2465:
2460:
2456:
2452:
2441:
2437:
2419:
2412:
2406:
2399:
2392:
2381:
2374:
2370:
2359:
2349:
2339:
2330:
2321:
2312:
2303:
2296:
2287:
2286:
2285:
2284:
2280:
2276:
2264:
2260:
2249:
2244:
2238:
2221:
2217:
2212:
2208:
2204:
2196:
2190:
2181:
2177:
2172:
2168:
2164:
2150:
2126:
2122:
2115:
2108:
2104:
2092:
2086:
2082:
2074:
2070:
2063:
2059:
2055:
2044:
2042:
2038:
2028:
2026:
2020:
2012:
2007:
1999:
1995:1 + log|
1992:
1987:
1985:
1973:
1969:
1965:
1961:
1957:
1953:
1943:
1941:
1937:
1933:
1929:
1919:
1899:
1893:
1890:
1887:
1881:
1875:
1872:
1869:
1866:
1864:
1856:
1850:
1840:
1834:
1831:
1828:
1822:
1816:
1813:
1811:
1803:
1797:
1763:
1759:
1755:
1750:
1746:
1742:
1735:
1731:
1712:
1708:
1704:
1700:
1693:
1689:
1682:
1678:
1654:
1650:
1646:
1642:
1632:
1624:
1620:
1616:
1612:
1589:
1585:
1581:
1573:
1567:
1565:
1557:
1551:
1547:
1538:
1532:
1528:
1521:
1517:
1510:
1506:
1499:
1495:
1491:
1482:
1473:
1467:
1463:
1459:
1455:
1450:
1441:
1439:
1429:
1425:
1421:
1413:
1409:
1405:
1398:
1379:
1376:
1371:
1367:
1363:
1360:
1357:
1352:
1348:
1332:
1328:
1324:
1318:
1314:
1307:
1303:
1295:
1253:
1249:
1228:
1224:
1220:
1217:
1214:
1209:
1205:
1201:
1198:
1195:
1192:
1189:
1184:
1180:
1176:
1173:
1170:
1165:
1161:
1150:
1140:
1136:
1132:
1128:
1118:
1110:
1106:
1102:
1098:
1091:
1087:
1076:
1072:
1068:
1063:
1056:
1050:
1048:
1044:
1034:
1032:
1028:
1024:
1020:
1016:
1012:
1008:
1004:
1003:
997:
995:
994:
988:
985:
981:
977:
973:
969:
965:
961:
957:
953:
950:
946:
941:
939:
934:(1.7 + log Δ)
931:
927:
923:
919:
915:
909:
904:
900:
894:
888:
884:
882:
877:
873:
871:
865:
863:
859:
855:
851:
850:
844:
830:
826:
819:
811:
808:
805:
802:
799:
796:
792:
782:
777:
760:
754:
751:
745:
737:
734:
731:
728:
725:
722:
718:
710:; obviously,
694:
686:
683:
675:
661:
655:
647:
644:
641:
638:
635:
632:
628:
618:
613:
597:
594:
588:
585:
582:
559:
556:
553:
533:
530:
527:
519:
515:
511:
506:
504:
500:
496:
492:
488:
487:spanning tree
484:
480:
476:
475:
464:
447:
439:
436:
428:
414:
408:
402:
393:
388:
372:
366:
363:
360:
352:
336:
333:
330:
327:
318:
304:
301:
295:
292:
289:
266:
263:
260:
240:
234:
231:
228:
220:
204:
201:
198:
190:
184:
180:
176:
165:
163:
159:
155:
150:
148:
143:
136:
130:
126:
122:
119:
106:
102:
96:
91:
83:
78:
73:
67:
61:
55:
49:
45:
41:
37:
28:
22:
4498:
4468:
4436:
4396:
4392:Algorithmica
4390:
4356:
4352:
4318:
4287:
4260:
4254:
4212:
4183:
4179:
4163:
4159:
4145:(2): 75–83,
4142:
4138:
4106:
4086:
4080:
4038:
4001:
3976:
3972:
3947:
3943:
3918:
3912:
3885:
3881:
3860:
3856:
3822:
3797:
3772:(2): 73–76,
3769:
3765:
3730:
3724:
3694:
3682:
3670:
3658:
3646:
3634:
3622:
3610:
3598:
3586:
3574:
3547:
3514:
3510:
3489:
3477:
3450:
3446:
3436:
3424:
3412:
3400:
3388:
3338:
3307:
3298:
3288:
3284:
3280:
3265:
3253:
3238:
3231:
3224:
3213:
3209:
3202:
3178:
3094:
3091:
3074:
3067:
3060:
3056:
3037:
3022:
3018:
3004:
2994:
2987:
2983:
2968:
2964:
2960:
2953:
2946:
2942:
2938:
2931:
2925:
2921:
2914:
2908:
2904:
2900:
2893:
2887:
2883:
2879:
2875:
2871:
2867:
2863:
2842:
2836:
2830:
2821:
2817:
2812:
2808:
2804:
2794:
2790:
2784:
2780:
2776:
2770:
2766:
2758:
2752:
2735:
2725:
2721:
2690:
2686:
2682:
2676:
2672:
2670:there is an
2666:
2662:
2654:
2648:
2632:
2628:
2621:
2617:
2612:
2608:
2604:
2601:
2570:
2566:
2562:
2556:
2552:
2545:
2541:
2534:
2530:
2526:
2520:
2516:
2512:
2505:
2501:
2497:
2490:
2486:
2482:
2467:
2463:
2458:
2454:
2450:
2439:
2435:
2431:
2417:
2410:
2404:
2397:
2390:
2379:
2372:
2368:
2357:
2353:= {3, 5, 6}.
2347:
2337:
2328:
2319:
2310:
2307:= {1, 2, 5},
2301:
2294:
2262:
2258:
2250:
2242:
2236:
2219:
2215:
2210:
2206:
2202:
2194:
2188:
2179:
2175:
2170:
2166:
2162:
2151:
2124:
2120:
2113:
2106:
2102:
2084:
2080:
2072:
2068:
2061:
2057:
2053:
2050:
2041:L-reductions
2034:
2031:L-reductions
2018:
2010:
2005:
1997:
1988:
1960:L-reductions
1949:
1928:Richard Karp
1925:
1761:
1757:
1753:
1751:
1744:
1740:
1733:
1729:
1710:
1706:
1702:
1698:
1691:
1687:
1680:
1676:
1652:
1648:
1644:
1640:
1633:
1622:
1618:
1614:
1610:
1587:
1583:
1579:
1577:
1571:
1549:
1545:
1530:
1526:
1519:
1515:
1508:
1504:
1497:
1493:
1483:
1465:
1461:
1457:
1453:
1448:
1447:is called a
1442:
1427:
1423:
1419:
1411:
1407:
1403:
1399:
1330:
1326:
1322:
1316:
1312:
1305:
1301:
1293:
1251:
1247:
1148:
1138:
1134:
1130:
1126:
1119:
1108:
1104:
1100:
1096:
1089:
1085:
1074:
1070:
1066:
1064:
1060:
1054:
1040:
1030:
1026:
1022:
1018:
1014:
1010:
1006:
1000:
998:
991:
989:
987:considered.
979:
975:
971:
963:
959:
955:
951:
944:
942:
937:
929:
925:
921:
917:
913:
907:
902:
898:
892:
886:
880:
879:
875:
869:
868:
866:
861:
857:
853:
848:
845:
784:is at least
780:
778:
616:
611:
517:
513:
509:
507:
502:
498:
494:
490:
482:
472:
470:
391:
386:
350:
319:
218:
217:is called a
191:of vertices
182:
178:
174:
171:
151:
141:
134:
104:
100:
94:
92:
81:
76:
71:
65:
59:
53:
51:is a subset
47:
39:
36:graph theory
33:
4201:1721.1/1201
4117:, Stockholm
3567:Kann (1992)
3405:West (2001)
3040:= {1, 3, 4}
2581:split graph
2575:. That is,
1940:NP-complete
1936:NP-complete
1930:proved the
1766:of a graph
1592:of a graph
1570:Domination
1079:of a graph
1053:Domination
118:NP-complete
4511:Categories
3979:(2): 281,
3740:cs/0207066
3709:References
3373:Nonblocker
3341:nonblocker
2748:such that
2680:such that
2130:such that
1638:for which
1490:line graph
1124:for which
1021:is not in
572:such that
279:such that
112:and input
4361:CiteSeerX
4071:247570676
3531:1439-6912
3469:0097-3165
3327:forbidden
3136:−
3124:≤
3007:= {1, 4}.
2550:for each
2334:= {3, 4},
2016:for some
2008:log|
1968:see below
1942:as well.
1894:γ
1888:≥
1873:γ
1867:≥
1835:γ
1829:≥
1817:γ
1814:≥
1470:in every
1361:…
1218:…
1174:…
852:is a set
793:γ
755:γ
752:≥
719:γ
629:γ
595:∈
557:∈
531:∈
518:including
493:in which
479:connected
403:γ
370:∖
364:∈
302:∈
264:∈
238:∖
232:∈
202:⊆
4497:(2001),
4487:38201061
4457:37903553
4414:1903/830
4279:16082154
4242:15457604
4123:citation
4037:(1979).
3814:(2006),
3539:43510417
3347:See also
3256:(1.7159)
3241:(1.5048)
3234:(1.5264)
3227:(1.5137)
3164:, where
3031:. Given
2816: :
2707:; hence
2616: :
2462: :
2360:= {3, 5}
2214: :
2174: :
2091:universe
1537:matching
1443:A graph
1290:. Then
1245:, where
912:admit a
467:Variants
4423:1249122
4209:Raz, R.
4063:0519066
3993:5232238
3964:2489447
3935:1186651
3904:1432221
3305:√
3097:(log Δ)
3025:, 3, 4}
2802:. Then
2644:, with
2636:, then
2602:Now if
2232:, with
2160:, then
2152:Now if
2119:, ...,
2023:unless
1952:NP-hard
1922:History
1647:) <
1395:
1337:
1320:, then
1243:
1153:
1147:be the
1133:) <
4485:
4475:
4455:
4445:
4421:
4363:
4333:
4306:
4277:
4240:
4230:
4069:
4061:
4051:
4019:
4004:ANALCO
3991:
3962:
3933:
3902:
3837:
3757:488501
3755:
3537:
3529:
3467:
3249:1.7159
2846:|
2828:|
2762:|
2750:|
2658:|
2646:|
2595:is an
2589:clique
2246:|
2234:|
2198:|
2186:|
2025:P = NP
2021:> 0
2014:|
2001:|
1934:to be
1738:, but
1661:, let
1488:, its
1335:since
1298:since
1279:, and
1254:> 1
966:, the
949:subset
189:subset
75:. The
63:is in
42:for a
4419:S2CID
4387:(PDF)
4275:S2CID
4238:S2CID
4111:(PDF)
3989:S2CID
3960:S2CID
3931:S2CID
3853:(PDF)
3819:(PDF)
3753:S2CID
3735:arXiv
3535:S2CID
3380:Notes
3320:to a
2587:is a
2579:is a
2066:with
1747:) = n
1736:) = 1
1694:) = 2
1683:) = 1
1436:is a
1296:) = 2
947:is a
481:. If
44:graph
4483:OCLC
4473:ISBN
4453:OCLC
4443:ISBN
4331:ISBN
4304:ISBN
4228:ISBN
4129:link
4067:OCLC
4049:ISBN
4017:ISBN
3835:ISBN
3527:ISSN
3465:ISSN
3187:and
2951:and
2764:and
2699:and
2591:and
2560:and
2519:} ∈
2432:Let
2403:4 ∈
2396:3 ∈
2389:4 ∈
2345:and
1752:The
1723:-by-
1705:) /
1669:-by-
1617:) ≤
1578:The
1460:) =
1422:) =
1406:) =
1329:) =
1103:) ≤
1065:The
968:star
512:(or
317:.
187:, a
103:) ≤
93:The
38:, a
4409:hdl
4401:doi
4371:doi
4323:doi
4296:doi
4265:doi
4220:doi
4196:hdl
4188:doi
4168:doi
4147:doi
4091:doi
4009:doi
3981:doi
3952:doi
3923:doi
3890:doi
3886:164
3865:doi
3861:359
3827:doi
3774:doi
3745:doi
3519:doi
3455:doi
3451:102
3174:APX
3059:= {
3021:= {
2986:= {
2959:= {
2937:= {
2920:= {
2899:= {
2886:},
2866:= {
2807:= {
2798:of
2607:= {
2485:= (
2453:= {
2371:= {
2205:= {
2165:= {
2145:in
2105:= {
2096:is
2056:= (
1774:of
1758:iγi
1600:of
1558:in
1539:in
1477:of
1451:if
1432:if
1333:+ 1
999:An
970:of
962:in
954:of
910:− 1
665:min
614:of
489:of
418:min
389:of
177:= (
123:in
34:In
4513::
4481:,
4451:,
4417:,
4407:,
4397:20
4395:,
4389:,
4369:,
4355:,
4329:,
4302:,
4290:,
4273:,
4261:29
4259:,
4236:,
4226:,
4194:,
4184:39
4182:,
4164:43
4162:,
4143:89
4141:,
4125:}}
4121:{{
4087:86
4085:,
4065:.
4059:MR
4057:.
4047:.
4033:;
4015:,
3987:,
3977:36
3975:,
3958:,
3946:,
3929:,
3919:56
3917:,
3900:MR
3898:,
3884:,
3859:,
3855:,
3833:,
3821:,
3810:;
3791:;
3770:23
3768:,
3751:,
3743:,
3731:51
3729:,
3719:;
3559:^
3533:.
3525:.
3515:27
3513:.
3501:^
3463:.
3449:.
3445:.
3272:W
3258:.
3212:(2
3195:.
3080:}.
3073:,
3066:,
2993:,
2971:}.
2967:,
2963:,
2949:},
2945:,
2941:,
2928:},
2924:,
2911:},
2907:,
2903:,
2882:,
2878:,
2874:,
2870:,
2848:.
2820:∈
2793:∈
2783:∩
2779:∈
2769:⊆
2733:.
2724:∈
2685:∈
2675:∈
2665:∈
2631:⊆
2620:∈
2599:.
2583::
2565:∈
2555:∈
2548:}
2544:,
2533:∈
2529:,
2515:,
2504:∪
2500:=
2489:,
2470:};
2466:∈
2438:,
2416:∈
2385:}.
2378:,
2261:,
2248:.
2218:∈
2178:∈
2149:.
2112:,
2083:,
2075:},
2060:,
2027:.
1986:.
1786::
1749:.
1730:iγ
1707:iγ
1677:iγ
1641:iγ
1631:.
1611:iγ
1584:iγ
1572:of
1440:.
1418:γ(
1402:γ(
1315:≤
1308:}
1304:,
1292:γ(
1271:,
1250:,
1117:.
1055:by
1033:.
990:A
943:A
867:A
843:.
779:A
776:.
662::=
508:A
471:A
463:.
415::=
181:,
164:.
133:γ(
99:γ(
90:.
80:γ(
4503:.
4490:.
4460:.
4426:.
4411::
4403::
4378:.
4373::
4357:4
4340:.
4325::
4313:.
4298::
4282:.
4267::
4245:.
4222::
4198::
4190::
4170::
4154:.
4149::
4133:.
4131:)
4100:.
4093::
4073:.
4026:.
4011::
3996:.
3983::
3967:.
3954::
3948:5
3938:.
3925::
3907:.
3892::
3867::
3844:.
3829::
3802:.
3783:.
3776::
3760:.
3747::
3737::
3701:.
3689:.
3677:.
3665:.
3653:.
3641:.
3629:.
3617:.
3605:.
3593:.
3581:.
3554:.
3541:.
3521::
3496:.
3484:.
3471:.
3457::
3431:.
3419:.
3395:.
3314:n
3308:k
3301:k
3294:f
3289:n
3287:)
3285:k
3283:(
3281:f
3268:k
3254:O
3239:O
3232:O
3225:O
3216:)
3214:n
3210:O
3205:n
3170:M
3166:N
3150:1
3147:+
3144:M
3141:2
3133:1
3130:+
3127:N
3119:g
3115:d
3103:g
3101:d
3095:O
3078:4
3075:S
3071:3
3068:S
3064:1
3061:S
3057:C
3052:X
3048:I
3044:D
3038:X
3033:D
3029:G
3023:a
3019:D
3005:D
3000:}
2998:4
2995:S
2991:1
2988:S
2984:C
2969:e
2965:d
2961:c
2957:4
2954:S
2947:d
2943:c
2939:b
2935:3
2932:S
2926:b
2922:a
2918:2
2915:S
2909:c
2905:b
2901:a
2897:1
2894:S
2888:I
2884:e
2880:d
2876:c
2872:b
2868:a
2864:U
2843:D
2837:X
2831:C
2824:}
2822:X
2818:i
2813:i
2809:S
2805:C
2800:u
2795:I
2791:i
2785:U
2781:D
2777:u
2771:I
2767:X
2759:D
2753:X
2746:X
2742:G
2738:D
2731:D
2726:I
2722:i
2717:D
2713:i
2709:u
2705:G
2701:i
2697:u
2691:i
2687:S
2683:u
2677:D
2673:i
2667:U
2663:u
2655:C
2649:D
2642:G
2638:D
2633:I
2629:D
2624:}
2622:D
2618:i
2613:i
2609:S
2605:C
2593:U
2585:I
2577:G
2571:i
2567:S
2563:u
2557:I
2553:i
2546:u
2542:i
2540:{
2535:I
2531:j
2527:i
2521:E
2517:j
2513:i
2511:{
2506:U
2502:I
2498:V
2493:)
2491:E
2487:V
2483:G
2478:I
2474:U
2468:I
2464:i
2459:i
2455:S
2451:S
2446:U
2442:)
2440:U
2436:S
2434:(
2421:.
2418:C
2414:3
2411:S
2405:U
2398:D
2391:V
2383:5
2380:S
2376:3
2373:S
2369:C
2364:G
2358:D
2351:6
2348:S
2341:5
2338:S
2332:4
2329:S
2323:3
2320:S
2314:2
2311:S
2305:1
2302:S
2295:U
2290:G
2265:)
2263:S
2259:U
2257:(
2253:G
2243:C
2237:D
2230:G
2226:D
2222:}
2220:D
2216:v
2211:v
2207:S
2203:C
2195:D
2189:C
2182:}
2180:D
2176:v
2171:v
2167:S
2163:C
2158:G
2154:D
2147:G
2143:v
2139:v
2134:v
2132:S
2128:}
2125:n
2121:S
2117:2
2114:S
2110:1
2107:S
2103:S
2098:V
2094:U
2087:)
2085:S
2081:U
2079:(
2073:n
2069:V
2064:)
2062:E
2058:V
2054:G
2019:c
2011:V
2006:c
1998:V
1903:)
1900:G
1897:(
1891:i
1885:)
1882:G
1879:(
1876:i
1870:i
1860:)
1857:G
1854:(
1851:i
1844:)
1841:G
1838:(
1832:i
1826:)
1823:G
1820:(
1807:)
1804:G
1801:(
1798:i
1784:G
1780:A
1776:G
1772:A
1768:G
1764:)
1762:G
1760:(
1745:G
1743:(
1741:γ
1734:G
1732:(
1725:n
1721:n
1717:G
1713:)
1711:G
1709:(
1703:G
1701:(
1699:γ
1692:G
1690:(
1688:γ
1681:G
1679:(
1671:n
1667:n
1663:G
1659:n
1655:)
1653:G
1651:(
1649:γ
1645:G
1643:(
1636:G
1629:G
1625:)
1623:G
1621:(
1619:γ
1615:G
1613:(
1606:A
1602:G
1598:A
1594:G
1590:)
1588:G
1586:(
1560:G
1552:)
1550:G
1548:(
1546:L
1541:G
1533:)
1531:G
1529:(
1527:L
1522:)
1520:G
1518:(
1516:L
1511:)
1509:G
1507:(
1505:L
1500:)
1498:G
1496:(
1494:L
1486:G
1479:G
1475:H
1468:)
1466:H
1464:(
1462:i
1458:H
1456:(
1454:γ
1445:G
1434:G
1430:)
1428:G
1426:(
1424:i
1420:G
1414:)
1412:G
1410:(
1408:i
1404:G
1383:}
1380:b
1377:,
1372:p
1368:x
1364:,
1358:,
1353:1
1349:x
1345:{
1331:p
1327:G
1325:(
1323:i
1317:q
1313:p
1306:b
1302:a
1300:{
1294:G
1287:j
1285:y
1281:b
1277:b
1273:a
1269:a
1264:i
1262:x
1258:G
1252:q
1248:p
1229:q
1225:y
1221:,
1215:,
1210:1
1206:y
1202:,
1199:b
1196:,
1193:a
1190:,
1185:p
1181:x
1177:,
1171:,
1166:1
1162:x
1145:G
1141:)
1139:G
1137:(
1135:i
1131:G
1129:(
1127:γ
1122:G
1115:G
1111:)
1109:G
1107:(
1105:i
1101:G
1099:(
1097:γ
1092:)
1090:G
1088:(
1086:i
1081:G
1077:)
1075:G
1073:(
1071:i
1031:v
1027:D
1023:D
1019:u
1017:(
1015:u
1011:D
1007:v
980:D
976:v
972:v
964:V
960:v
956:V
952:D
938:k
930:k
926:k
922:k
918:k
914:k
908:k
903:k
899:k
895:)
893:n
887:k
881:k
876:k
870:k
862:D
858:D
854:D
831:2
827:/
823:)
820:G
817:(
812:g
809:n
806:o
803:r
800:t
797:s
764:)
761:G
758:(
749:)
746:G
743:(
738:g
735:n
732:o
729:r
726:t
723:s
698:}
695:G
687:D
684::
680:|
676:D
672:|
668:{
659:)
656:G
653:(
648:g
645:n
642:o
639:r
636:t
633:s
617:G
598:E
592:)
589:v
586:,
583:u
580:(
560:D
554:v
534:V
528:u
503:T
499:T
495:S
491:G
483:S
451:}
448:G
440:D
437::
433:|
429:D
425:|
421:{
412:)
409:G
406:(
392:G
373:D
367:V
361:u
351:D
337:=
334:V
331:=
328:D
305:E
299:)
296:v
293:,
290:u
287:(
267:D
261:v
241:D
235:V
229:u
205:V
199:D
185:)
183:E
179:V
175:G
142:G
137:)
135:G
114:K
110:G
105:K
101:G
88:G
84:)
82:G
72:D
66:D
60:G
54:D
48:G
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
