Planar graph classes with the independent set problem solvable in polynomial time

被引：1
作者：
Alekseev V.E. [1 ]
Malyshev D.S. [1 ]
机构：
[1] Department of Computational Mathematics and Cybernetics, State University of Nizhnii Novgorod, Nizhnii Novgorod 603950
来源：
Journal of Applied and Industrial Mathematics | 2009年 / 3卷 / 1期
关键词：
Polynomial Time; Planar Graph; Vertex Covering; Boundary Class; Independence Number;
D O I：
10.1134/S1990478909010013
中图分类号：
学科分类号：
摘要：
The polynomial solvability of the independent set problem is proved for an infinite family of subsets of the class of planar graphs. © Pleiades Publishing, Ltd. 2009.
引用
收藏
页码：1 / 4
页数：3
相关论文
共 6 条
  • [1] Alekseev V.E., On Compressed Graphs, Problemy Kibernet., 36, pp. 23-31, (1979)
  • [2] Alekseev V.E., On Influence of Local Constraints on the Complexity of the Definition of Graph Independence Number, Combinatoric and Algebraic Methods in Applied Mathematics, pp. 3-13, (1983)
  • [3] Alekseev V.E., On Easy and Hard Hereditary Classes of Graphs with Respect to the Independent Set Problem, Discrete Appl. Math., 132, 1-3, pp. 17-26, (2004)
  • [4] Bodlaender H.L., Dynamic Programming on Graphs with Bounded Treewidth, Lecture Notes in Computer Sciences, 317, pp. 105-118, (1988)
  • [5] Lozin V., Milanic M., A Polynomial Algorithm for Finding an Independent Set of Maximum Weight in Fork-Free Graphs, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2007)
  • [6] Robertson N., Seymour P., Graph Minors. III. Planar Treewidth, J. Combin. Theory, Ser. B, 36, 1, pp. 49-64, (1984)
1