64:
183:. For instance, the series–parallel graphs are a subfamily of the partial 2-trees, and more strongly a graph is a partial 2-tree if and only if each of its
367:
84:
95:, and their single forbidden minor is a triangle. For the partial 2-trees the single forbidden minor is the
456:
285:
Arnborg, S.; Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial
168:
451:
103:. For partial 3-trees there are four forbidden minors: the complete graph on five vertices, the
47:
combinatorial problems on graphs are solvable in polynomial time when restricted to the partial
199:
316:; Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs",
184:
8:
203:
132:
99:
on four vertices. However, the number of forbidden minors increases for larger values of
92:
377:
344:, Lecture Notes in Computer Science, vol. 317, Springer-Verlag, pp. 105–118,
337:
191:
180:
136:
418:(1998), "All structured programs have small tree width and good register allocation",
397:
363:
329:
303:
172:
427:
401:
393:
353:
345:
325:
298:
112:
63:
159:
is the bound on the treewidth. Families of graphs with this property include the
124:
88:
96:
349:
445:
415:
313:
432:
164:
160:
108:
17:
342:
Proc. 15th
International Colloquium on Automata, Languages and Programming
176:
80:
104:
406:
358:
148:
36:
195:
44:
340:(1988), "Dynamic programming on graphs with bounded treewidth",
202:
also have bounded treewidth, which allows certain tasks such as
87:, this family can be characterized in terms of a finite set of
29:
127:
for arbitrary graphs may be solved efficiently for partial
28:
is a type of graph, defined either as a subgraph of a
215:
284:
248:
443:
384:-arboretum of graphs with bounded treewidth",
311:
252:
142:
376:
336:
256:
236:
221:
431:
405:
357:
302:
79:-trees are closed under the operation of
151:, then it is a subfamily of the partial
62:
444:
414:
268:
118:
91:. The partial 1-trees are exactly the
232:
230:
206:to be performed efficiently on them.
107:with six vertices, the eight-vertex
67:Forbidden minors for partial 3-trees
123:Many algorithmic problems that are
51:-trees, for bounded values of
13:
227:
147:If a family of graphs has bounded
14:
468:
249:Arnborg & Proskurowski (1989)
58:
262:
253:Bern, Lawler & Wong (1987)
242:
1:
398:10.1016/S0304-3975(97)00228-4
277:
386:Theoretical Computer Science
330:10.1016/0196-6774(87)90039-3
304:10.1016/0166-218X(89)90031-0
291:Discrete Applied Mathematics
7:
420:Information and Computation
10:
473:
143:Related families of graphs
350:10.1007/3-540-19488-6_110
85:Robertson–Seymour theorem
209:
83:, and therefore, by the
71:For any fixed constant
433:10.1006/inco.1997.2697
185:biconnected components
169:series–parallel graphs
68:
318:Journal of Algorithms
66:
187:is series–parallel.
380:(1998), "A partial
378:Bodlaender, Hans L.
338:Bodlaender, Hans L.
204:register allocation
200:structured programs
192:control-flow graphs
181:Apollonian networks
137:tree decompositions
133:dynamic programming
119:Dynamic programming
115:with ten vertices.
35:or as a graph with
457:Graph minor theory
173:outerplanar graphs
69:
369:978-3-540-19488-0
257:Bodlaender (1988)
237:Bodlaender (1998)
222:Bodlaender (1988)
139:of these graphs.
464:
436:
435:
410:
409:
372:
361:
332:
307:
306:
272:
266:
260:
246:
240:
234:
225:
219:
113:pentagonal prism
105:octahedral graph
89:forbidden minors
472:
471:
467:
466:
465:
463:
462:
461:
442:
441:
440:
370:
280:
275:
267:
263:
247:
243:
235:
228:
220:
216:
212:
194:arising in the
145:
121:
61:
12:
11:
5:
470:
460:
459:
454:
452:Graph families
439:
438:
426:(2): 159–181,
416:Thorup, Mikkel
412:
374:
368:
334:
324:(2): 216–235,
309:
281:
279:
276:
274:
273:
261:
241:
226:
213:
211:
208:
155:-trees, where
144:
141:
120:
117:
97:complete graph
75:, the partial
60:
57:
9:
6:
4:
3:
2:
469:
458:
455:
453:
450:
449:
447:
434:
429:
425:
421:
417:
413:
408:
403:
399:
395:
392:(1–2): 1–45,
391:
387:
383:
379:
375:
371:
365:
360:
355:
351:
347:
343:
339:
335:
331:
327:
323:
319:
315:
314:Lawler, E. L.
312:Bern, M. W.;
310:
305:
300:
296:
292:
288:
283:
282:
270:
269:Thorup (1998)
265:
258:
254:
250:
245:
238:
233:
231:
223:
218:
214:
207:
205:
201:
197:
193:
188:
186:
182:
178:
174:
170:
166:
165:pseudoforests
162:
161:cactus graphs
158:
154:
150:
140:
138:
134:
130:
126:
116:
114:
110:
106:
102:
98:
94:
90:
86:
82:
78:
74:
65:
56:
54:
50:
46:
42:
39:at most
38:
34:
32:
27:
25:
19:
423:
419:
389:
385:
381:
341:
321:
317:
297:(1): 11–24,
294:
290:
286:
264:
244:
217:
189:
177:Halin graphs
156:
152:
146:
135:, using the
128:
122:
109:Wagner graph
100:
81:graph minors
76:
72:
70:
59:Graph minors
52:
48:
40:
30:
23:
21:
18:graph theory
15:
196:compilation
125:NP-complete
446:Categories
407:1874/18312
359:1874/16258
278:References
131:-trees by
111:, and the
289:-trees",
149:treewidth
37:treewidth
22:partial
93:forests
45:NP-hard
43:. Many
366:
179:, and
210:Notes
33:-tree
26:-tree
364:ISBN
190:The
20:, a
428:doi
424:142
402:hdl
394:doi
390:209
354:hdl
346:doi
326:doi
299:doi
198:of
16:In
448::
422:,
400:,
388:,
362:,
352:,
320:,
295:23
293:,
255:;
251:;
229:^
175:,
171:,
167:,
163:,
55:.
437:.
430::
411:.
404::
396::
382:k
373:.
356::
348::
333:.
328::
322:8
308:.
301::
287:k
271:.
259:.
239:.
224:.
157:k
153:k
129:k
101:k
77:k
73:k
53:k
49:k
41:k
31:k
24:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
