QUICKLY EXCLUDING A FOREST

被引:68
作者
BIENSTOCK, D
ROBERTSON, N
SEYMOUR, P
THOMAS, R
机构
[1] BELL COMMUN RES INC,MORRISTOWN,NJ 07960
[2] OHIO STATE UNIV,DEPT MATH,COLUMBUS,OH 43210
[3] RUTGERS STATE UNIV,CTR DIMACS,NEW BRUNSWICK,NJ 08903
关键词
D O I
10.1016/0095-8956(91)90068-U
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that for every forest F, every graph with no minor isomorphic to F has path-width at most |V(F)| -2. © 1991.
引用
收藏
页码:274 / 283
页数:10
相关论文
共 7 条
[1]  
BIENSTOCK D, IN PRESS J ALGORITHM
[2]   INTERVAL-GRAPHS AND SEARCHING [J].
KIROUSIS, LM ;
PAPADIMITRIOU, CH .
DISCRETE MATHEMATICS, 1985, 55 (02) :181-184
[3]   SEARCHING AND PEBBLING [J].
KIROUSIS, LM ;
PAPADIMITRIOU, CH .
THEORETICAL COMPUTER SCIENCE, 1986, 47 (02) :205-218
[4]  
LAPAUGH A, 1982, 335 PRINC U DEP EL E
[5]   GRAPH MINORS .1. EXCLUDING A FOREST [J].
ROBERTSON, N ;
SEYMOUR, PD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 35 (01) :39-61
[6]   GRAPH MINORS .10. OBSTRUCTIONS TO TREE-DECOMPOSITION [J].
ROBERTSON, N ;
SEYMOUR, PD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 52 (02) :153-190
[7]  
SEYMOUR PD, UNPUB GROUP SEARCHIN