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