357:
to test whether there exists a connected dominating set with size less than a given threshold, or equivalently to test whether there exists a spanning tree with at least a given number of leaves. Therefore, it is believed that the minimum connected dominating set problem and the maximum leaf spanning
399:
of these algorithms (intuitively, a number of leaves up to which the problem can be solved within a reasonable amount of time) has gradually increased, as algorithms for the problem have improved, to approximately 37, and it has been suggested that at least 50 should be achievable.
792:
Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three", Proceedings of the First Japan
Conference on Graph Theory and Applications (Hakone, 1986),
344:
Therefore, in any graph, the sum of the connected domination number and the max leaf number equals the total number of vertices. Computationally, this implies that determining the connected domination number is equally difficult as finding the max leaf number.
435:. In this application, a small connected dominating set is used as a backbone for communications, and nodes that are not in this set communicate by passing messages through neighbors that are in the set.
498:
Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket (2009), "The complexity ecology of parameters: an illustration using bounded max leaf number",
680:
Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Raible, Daniel; Rossmanith, Peter (2011), "An exact algorithm for the maximum leaf spanning tree problem",
751:; McCartin, Catherine; Rosamond, Frances A.; Stege, Ulrike (2000), "Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems",
238:
878:
365:
is not the same as approximating the other to the same ratio. There exists an approximation for the minimum connected dominating set that achieves a factor of
361:
When viewed in terms of approximation algorithms, connected domination and maximum leaf spanning trees are not the same: approximating one to within a given
768:
664:
148:
incident to them. A maximum leaf spanning tree is a spanning tree that has the largest possible number of leaves among all spanning trees of
374:
848:
608:
Galbiati, G.; Maffioli, F.; Morzenti, A. (1994), "A short note on the approximability of the maximum leaves spanning tree problem",
637:
795:
395:, meaning that it can be solved in time exponential in the number of leaves but only polynomial in the input graph size. The
888:
833:
Proceedings of the 3rd
International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications
439:
883:
831:
Wu, J.; Li, H. (1999), "On calculating connected dominating set for efficient routing in ad hoc wireless networks",
635:
Solis-Oba, Roberto (1998), "2-approximation algorithm for finding a spanning tree with maximum number of leaves",
445:: several NP-hard optimization problems may be solved in polynomial time for graphs of bounded max leaf number.
392:
407:
three, the connected dominating set and its complementary maximum leaf spanning tree problem can be solved in
717:
Binkele-Raible, Daniel; Fernau, Henning (2014), "A parameterized measure-and-conquer analysis for finding a
412:
206:
432:
404:
362:
854:
590:
516:
369:, where Δ is the maximum degree of a vertex in G. The maximum leaf spanning tree problem is
844:
764:
660:
836:
804:
756:
689:
650:
642:
617:
580:
572:
543:
508:
454:
68:
29:
818:
778:
734:
703:
814:
774:
748:
730:
699:
655:
408:
641:, Lecture Notes in Computer Science, vol. 1461, Springer-Verlag, pp. 441–452,
563:
Guha, S.; Khuller, S. (1998), "Approximation algorithms for connected dominating sets",
416:
377:
is likely. However, it can be approximated to within a factor of 2 in polynomial time.
95:
872:
809:
755:, Lecture Notes in Comput. Sci., vol. 1974, Springer, Berlin, pp. 240–251,
621:
594:
548:
457:, a vertex that (when it exists) gives a minimum connected dominating set of size one
248:
134:
858:
475:
Sampathkumar, E.; Walikar, HB (1979), "The connected domination number of a graph",
534:
Douglas, Robert J. (1992), "NP-completeness and degree restricted spanning trees",
520:
17:
753:
FST-TCS 2000: Foundations of
Software Technology and Theoretical Computer Science
354:
115:
694:
512:
396:
760:
646:
442:
840:
576:
428:
370:
585:
130:
is the number of vertices in the minimum connected dominating set.
144:
has at least two leaves, vertices that have only one edge of
438:
The max leaf number has been employed in the development of
327:
Putting these two inequalities together proves the equality
427:
Connected dominating sets are useful in the computation of
160:
is the number of leaves in the maximum leaf spanning tree.
114:
is a connected dominating set with the smallest possible
723:
308:
that are not leaves form a connected dominating set of
263:, together with edges connecting each remaining vertex
210:
209:
638:
Proc. 6th
European Symposium on Algorithms (ESA'98)
247:is a connected dominating set, then there exists a
358:tree problem cannot be solved in polynomial time.
259:: form a spanning tree of the subgraph induced by
255:whose leaves include all vertices that are not in
232:
188:is its max leaf number, then the three quantities
28:are two closely related structures defined on an
411:, by transforming them into an instance of the
721:-leaf spanning tree in an undirected graph",
8:
808:
693:
654:
584:
547:
493:
491:
208:
172:is the connected domination number of an
467:
118:among all connected dominating sets of
879:Computational problems in graph theory
40:A connected dominating set of a graph
60:by a path that stays entirely within
7:
375:polynomial time approximation scheme
233:{\displaystyle \displaystyle n=d+l.}
14:
48:of vertices with two properties:
380:Both problems may be solved, on
108:minimum connected dominating set
656:11858/00-001M-0000-0014-7BD6-0
610:Information Processing Letters
391:. The maximum leaf problem is
86:or is adjacent to a vertex in
1:
810:10.1016/0012-365X(88)90226-9
682:Theoretical Computer Science
622:10.1016/0020-0190(94)90139-2
549:10.1016/0012-365X(92)90130-8
56:can reach any other node in
501:Theory of Computing Systems
296:In the other direction, if
124:connected domination number
905:
26:maximum leaf spanning tree
695:10.1016/j.tcs.2011.07.011
513:10.1007/s00224-009-9167-9
440:fixed-parameter tractable
393:fixed-parameter tractable
200:obey the simple equation
761:10.1007/3-540-44450-5_19
647:10.1007/3-540-68530-8_37
384:-vertex graphs, in time
300:is any spanning tree in
71:a connected subgraph of
22:connected dominating set
373:hard, implying that no
304:, then the vertices of
835:, ACM, pp. 7–14,
433:mobile ad hoc networks
413:matroid parity problem
234:
841:10.1145/313239.313261
403:In graphs of maximum
235:
889:NP-complete problems
796:Discrete Mathematics
536:Discrete Mathematics
207:
749:Fellows, Michael R.
363:approximation ratio
884:Graph connectivity
577:10.1007/PL00009201
477:J. Math. Phys. Sci
367:2 ln Δ + O(1)
312:. This shows that
279:. This shows that
230:
229:
82:either belongs to
770:978-3-540-41413-1
688:(45): 6290–6302,
666:978-3-540-64848-2
271:to a neighbor of
896:
863:
861:
828:
822:
821:
812:
803:(1–3): 355–360,
789:
783:
781:
745:
739:
737:
714:
708:
706:
697:
677:
671:
669:
658:
632:
626:
624:
605:
599:
597:
588:
560:
554:
552:
551:
531:
525:
523:
495:
486:
484:
472:
455:Universal vertex
390:
383:
368:
341:
326:
293:
239:
237:
236:
231:
78:Every vertex in
30:undirected graph
904:
903:
899:
898:
897:
895:
894:
893:
869:
868:
867:
866:
851:
830:
829:
825:
791:
790:
786:
771:
747:
746:
742:
716:
715:
711:
679:
678:
674:
667:
634:
633:
629:
607:
606:
602:
562:
561:
557:
533:
532:
528:
497:
496:
489:
474:
473:
469:
464:
451:
425:
417:linear matroids
409:polynomial time
385:
381:
366:
351:
328:
313:
280:
267:that is not in
205:
204:
166:
164:Complementarity
154:max leaf number
38:
12:
11:
5:
902:
900:
892:
891:
886:
881:
871:
870:
865:
864:
849:
823:
784:
769:
740:
729:(1): 179–200,
709:
672:
665:
627:
600:
571:(4): 374–387,
555:
542:(1–3): 41–47,
526:
507:(4): 822–848,
487:
466:
465:
463:
460:
459:
458:
450:
447:
424:
421:
350:
347:
241:
240:
228:
225:
222:
219:
216:
213:
176:-vertex graph
165:
162:
104:
103:
96:dominating set
76:
37:
34:
13:
10:
9:
6:
4:
3:
2:
901:
890:
887:
885:
882:
880:
877:
876:
874:
860:
856:
852:
850:1-58113-174-7
846:
842:
838:
834:
827:
824:
820:
816:
811:
806:
802:
798:
797:
788:
785:
780:
776:
772:
766:
762:
758:
754:
750:
744:
741:
736:
732:
728:
724:
720:
713:
710:
705:
701:
696:
691:
687:
683:
676:
673:
668:
662:
657:
652:
648:
644:
640:
639:
631:
628:
623:
619:
615:
611:
604:
601:
596:
592:
587:
582:
578:
574:
570:
566:
559:
556:
550:
545:
541:
537:
530:
527:
522:
518:
514:
510:
506:
502:
494:
492:
488:
482:
478:
471:
468:
461:
456:
453:
452:
448:
446:
444:
441:
436:
434:
430:
422:
420:
418:
414:
410:
406:
401:
398:
394:
388:
378:
376:
372:
364:
359:
356:
348:
346:
342:
339:
335:
331:
324:
320:
316:
311:
307:
303:
299:
294:
291:
287:
283:
278:
274:
270:
266:
262:
258:
254:
250:
249:spanning tree
246:
226:
223:
220:
217:
214:
211:
203:
202:
201:
199:
195:
191:
187:
183:
179:
175:
171:
163:
161:
159:
155:
151:
147:
143:
139:
136:
135:spanning tree
131:
129:
125:
121:
117:
113:
109:
101:
97:
93:
89:
85:
81:
77:
74:
70:
67:
63:
59:
55:
51:
50:
49:
47:
43:
35:
33:
31:
27:
23:
19:
832:
826:
800:
794:
787:
752:
743:
726:
722:
718:
712:
685:
681:
675:
636:
630:
616:(1): 45–49,
613:
609:
603:
568:
565:Algorithmica
564:
558:
539:
535:
529:
504:
500:
483:(6): 607–613
480:
476:
470:
437:
426:
423:Applications
402:
386:
379:
360:
352:
343:
337:
333:
329:
322:
318:
314:
309:
305:
301:
297:
295:
289:
285:
281:
276:
272:
268:
264:
260:
256:
252:
244:
242:
197:
193:
189:
185:
181:
177:
173:
169:
167:
157:
153:
149:
145:
141:
137:
132:
127:
123:
119:
111:
107:
105:
99:
91:
87:
83:
79:
72:
65:
61:
57:
53:
52:Any node in
45:
41:
39:
25:
21:
18:graph theory
15:
355:NP-complete
140:of a graph
116:cardinality
110:of a graph
90:. That is,
64:. That is,
36:Definitions
873:Categories
462:References
443:algorithms
397:klam value
349:Algorithms
595:263230631
44:is a set
859:59969437
586:1903/830
449:See also
317:−
288:−
182:n > 2
180:, where
819:0975556
779:1850108
735:3188035
704:2883043
521:4053586
429:routing
371:MAX-SNP
69:induces
857:
847:
817:
777:
767:
733:
702:
663:
593:
519:
405:degree
353:It is
196:, and
184:, and
152:. The
122:. The
24:and a
855:S2CID
591:S2CID
517:S2CID
389:(1.9)
94:is a
845:ISBN
765:ISBN
661:ISBN
431:for
415:for
133:Any
20:, a
837:doi
805:doi
757:doi
690:doi
686:412
651:hdl
643:doi
618:doi
581:hdl
573:doi
544:doi
540:105
509:doi
275:in
251:in
243:If
168:If
156:of
126:of
98:of
16:In
875::
853:,
843:,
815:MR
813:,
801:72
799:,
775:MR
773:,
763:,
731:MR
727:16
725:,
700:MR
698:,
684:,
659:,
649:,
614:52
612:,
589:,
579:,
569:20
567:,
538:,
515:,
505:45
503:,
490:^
481:13
479:,
419:.
336:+
332:=
321:≥
284:≥
192:,
106:A
32:.
862:.
839::
807::
782:.
759::
738:.
719:k
707:.
692::
670:.
653::
645::
625:.
620::
598:.
583::
575::
553:.
546::
524:.
511::
485:.
387:O
382:n
340:.
338:l
334:d
330:n
325:.
323:d
319:l
315:n
310:G
306:T
302:G
298:T
292:.
290:d
286:n
282:l
277:D
273:v
269:D
265:v
261:D
257:D
253:G
245:D
227:.
224:l
221:+
218:d
215:=
212:n
198:n
194:l
190:d
186:l
178:G
174:n
170:d
158:G
150:G
146:T
142:G
138:T
128:G
120:G
112:G
102:.
100:G
92:D
88:D
84:D
80:G
75:.
73:G
66:D
62:D
58:D
54:D
46:D
42:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.