NP-hard graph problems and boundary classes of graphs

被引：61
作者：
Alekseev, V. E. [1 ]
Boliac, R. [2 ]
Korobitsyn, D. V. [1 ]
Lozin, V. V. [2 ]
机构：
[1] Univ Nizhny Novgorod, Nizhnii Novgorod 603950, Russia
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
来源：
THEORETICAL COMPUTER SCIENCE | 2007年 / 389卷 / 1-2期
关键词：
computational complexity; hereditary class of graphs;
D O I：
10.1016/j.tcs.2007.09.013
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Any graph problem, which is NP-hard in general graphs, becomes polynomial-time solvable when restricted to graphs in special classes. When does a difficult problem become easy? To answer this question we study the notion of boundary classes. In the present paper we define this notion in its most general form, describe several approaches to identify boundary classes and apply them to various graph problems. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：219 / 236
页数：18
相关论文
共 45 条
[1]  
Alekseev V.E., 1983, COMBINATORIAL ALGEBR, V132, P3
[2]  
Alekseev V. E., 1992, DISKRET MAT, V4, P34
[3]   Boundary classes of graphs for the dominating set problem [J].
Alekseev, VE ;
Korobitsyn, DV ;
Lozin, VV .
DISCRETE MATHEMATICS, 2004, 285 (1-3) :1-6
[4]   On easy and hard hereditary classes of graphs with respect to the independent set problem [J].
Alekseev, VE .
DISCRETE APPLIED MATHEMATICS, 2003, 132 (1-3) :17-26
[5]   Some APX-completeness results for cubic graphs [J].
Alimonti, P ;
Kann, V .
THEORETICAL COMPUTER SCIENCE, 2000, 237 (1-2) :123-134
[6]   DISTANCE-HEREDITARY GRAPHS [J].
BANDELT, HJ ;
MULDER, HM .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) :182-208
[7]  
Beineke LW, 1970, J COMB THEORY, V9, P129, DOI 10.1016/S0021-9800(70)80019-9
[8]   ON THE TOPOLOGY OF THE GENETIC FINE STRUCTURE [J].
BENZER, S .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1959, 45 (11) :1607-1620
[9]  
Boliac R, 2004, ARS COMBINATORIA, V72, P241
[10]  
Boliac R, 2002, LECT NOTES COMPUT SC, V2518, P44
12345