17:
118:. A minimum maximal matching is a minimum edge dominating set; Figure (b) is an example of a minimum maximal matching. A minimum edge dominating set is not necessarily a minimum maximal matching, as illustrated in Figure (a); however, given a minimum edge dominating set
265:
225:
71:
is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph).
186:
show that finding a better than (7/6)-approximation is NP-hard. Schmied & Viehmann proved that the
Problem is UGC-hard to approximate to within any constant better than 3/2.
429:
169:
can be at worst 2 times as large as a smallest maximal matching, and a smallest maximal matching has the same size as the smallest edge dominating set.
275:
375:
Richard
Schmied & Claus Viehmann (2012), "Approximating edge dominating set in dense graphs", Theor. Comput. Sci. 414(1), pp. 92-99.
172:
Also the edge-weighted version of the problem can be approximated within factor 2, but the algorithm is considerably more complicated (
165:
with approximation factor 2: find any maximal matching. A maximal matching is an edge dominating set; furthermore, a maximal matching
288:
Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in
Appendix A1.1.
341:
Fujito, Toshihiro; Nagamochi, Hiroshi (2002), "A 2-approximation algorithm for the minimum weight edge dominating set problem",
196:
Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003),
424:
115:
162:
311:
221:
198:
Complexity and
Approximation: Combinatorial Optimization Problems and Their Approximability Properties
386:
316:
329:
299:
245:
209:
Minimum edge dominating set (optimisation version) is the problem GT3 in
Appendix B (page 370).
271:
212:
Minimum maximal matching (optimisation version) is the problem GT10 in
Appendix B (page 374).
350:
321:
261:
257:
237:
138:
Determining whether there is an edge dominating set of a given size for a given graph is an
108:
151:
406:
400:
111:
is always an edge dominating set. Figures (b) and (d) are examples of maximal matchings.
90:
80:
354:
291:
Minimum maximal matching (decision version) is the problem GT10 in
Appendix A1.1.
418:
249:
155:
25:
16:
363:
139:
390:
368:
Proceedings of the thirteenth annual ACM-SIAM symposium on
Discrete algorithms
241:
94:
114:
Furthermore, the size of a minimum edge dominating set equals the size of a
64:. Figures (a)–(d) are examples of edge dominating sets (thick red lines).
333:
143:
385:
Pierluigi
Crescenzi, Viggo Kann, MagnĂşs HalldĂłrsson, Marek Karpinski,
267:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
325:
142:
problem (and therefore finding a minimum edge dominating set is an
15:
302:; Gavril, Fanica (1980), "Edge dominating sets in graphs",
150:
show that the problem is NP-complete even in the case of a
226:"Approximation hardness of edge dominating set problems"
122:, it is easy to find a minimum maximal matching with |
183:
154:with maximum degree 3, and also in the case of a
147:
127:
173:
8:
81:Dominating set § Independent domination
60:. An edge dominating set is also known as a
391:"A compendium of NP optimization problems"
315:
364:"Edge dominating and hypomatchable sets"
134:Algorithms and computational complexity
430:Computational problems in graph theory
177:
230:Journal of Combinatorial Optimization
7:
56:is adjacent to at least one edge in
304:SIAM Journal on Applied Mathematics
161:There is a simple polynomial-time
14:
20:Examples of edge dominating sets.
184:ChlebĂk & ChlebĂková (2006)
148:Yannakakis & Gavril (1980)
1:
355:10.1016/S0166-218X(00)00383-8
343:Discrete Applied Mathematics
128:Yannakakis & Gavril 1980
52:such that every edge not in
401:Minimum Edge Dominating Set
174:Fujito & Nagamochi 2002
85:An edge dominating set for
69:minimum edge dominating set
446:
78:
242:10.1007/s10878-006-7908-0
407:Minimum Maximal Matching
116:minimum maximal matching
163:approximation algorithm
158:with maximum degree 3.
21:
362:Parekh, Ojas (2002),
79:Further information:
19:
425:NP-complete problems
126:| edges (see, e.g.,
300:Yannakakis, Mihalis
220:ChlebĂk, Miroslav;
62:line dominating set
30:edge dominating set
370:, pp. 287–291
104:) and vice versa.
22:
387:Gerhard Woeginger
277:978-0-7167-1045-5
262:Johnson, David S.
258:Garey, Michael R.
222:ChlebĂková, Janka
437:
371:
357:
336:
319:
280:
270:, W.H. Freeman,
252:
201:
109:maximal matching
445:
444:
440:
439:
438:
436:
435:
434:
415:
414:
382:
361:
340:
326:10.1137/0138030
317:10.1.1.477.4278
298:
278:
256:
219:
195:
192:
152:bipartite graph
136:
83:
77:
12:
11:
5:
443:
441:
433:
432:
427:
417:
416:
413:
412:
411:
410:
404:
395:
394:
381:
380:External links
378:
377:
376:
373:
359:
349:(3): 199–207,
338:
310:(3): 364–372,
295:
294:
293:
292:
289:
283:
282:
276:
254:
236:(3): 279–290,
216:
215:
214:
213:
210:
204:
203:
191:
188:
135:
132:
91:dominating set
76:
73:
44:) is a subset
36: = (
13:
10:
9:
6:
4:
3:
2:
442:
431:
428:
426:
423:
422:
420:
408:
405:
402:
399:
398:
397:
396:
392:
388:
384:
383:
379:
374:
369:
365:
360:
356:
352:
348:
344:
339:
335:
331:
327:
323:
318:
313:
309:
305:
301:
297:
296:
290:
287:
286:
285:
284:
279:
273:
269:
268:
263:
259:
255:
251:
247:
243:
239:
235:
231:
227:
223:
218:
217:
211:
208:
207:
206:
205:
199:
194:
193:
189:
187:
185:
181:
179:
175:
170:
168:
164:
159:
157:
153:
149:
145:
141:
133:
131:
129:
125:
121:
117:
112:
110:
105:
103:
99:
96:
92:
88:
82:
74:
72:
70:
65:
63:
59:
55:
51:
48: ⊆
47:
43:
39:
35:
31:
27:
18:
367:
346:
342:
307:
303:
266:
233:
229:
197:
182:
171:
166:
160:
156:planar graph
137:
123:
119:
113:
106:
101:
97:
86:
84:
68:
66:
61:
57:
53:
49:
45:
41:
37:
33:
32:for a graph
29:
26:graph theory
23:
178:Parekh 2002
140:NP-complete
419:Categories
200:, Springer
190:References
146:problem).
95:line graph
75:Properties
312:CiteSeerX
389:(2000),
264:(1979),
224:(2006),
93:for its
334:2100648
250:8024435
144:NP-hard
40:,
332:
314:
274:
248:
330:JSTOR
246:S2CID
89:is a
28:, an
272:ISBN
107:Any
351:doi
347:118
322:doi
238:doi
180:).
130:).
24:In
421::
366:,
345:,
328:,
320:,
308:38
306:,
260:;
244:,
234:11
232:,
228:,
176:;
67:A
409:.
403:,
393::
372:.
358:.
353::
337:.
324::
281:.
253:.
240::
202:.
167:M
124:D
120:D
102:G
100:(
98:L
87:G
58:D
54:D
50:E
46:D
42:E
38:V
34:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
