Independent set in P 5 -free graphs in polynomial time
作者： Yngve Villanger , Martin Vatshelle , Daniel Lokshantov
DOI:
关键词: Discrete mathematics 、 P versus NP problem 、 Mathematics 、 Independent set 、 Maximal independent set 、 Chordal graph 、 Combinatorics 、 Longest path problem 、 Matrix polynomial 、 Stable polynomial 、 Vertex cover
摘要: The Independent Set problem is NP-hard in general, however polynomial time algorithms exist for the on various specific graph classes. Over last couple of decades there has been a long sequence papers exploring boundary between and solvable cases. In particular complexity P5-free graphs received significant attention, list results showing that becomes sub-classes graphs. this paper we give first algorithm Our also works Weighted problem.
acm.org 参考文章(50)
Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs Journal of the ACM. ,vol. 41, pp. 153- 180 ,(1994) , 10.1145/174644.174650
Ton Kloks, Dieter Kratsch, Jeremy Spinrad, On treewidth and minimum fill-in of asteroidal triple-free graphs Theoretical Computer Science. ,vol. 175, pp. 309- 335 ,(1997) , 10.1016/S0304-3975(96)00206-X
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Lower bounds based on the Exponential Time Hypothesis Bulletin of The European Association for Theoretical Computer Science. ,vol. 3, pp. 467- 521 ,(2015) , 10.1007/978-3-319-21275-3_14
Chính T. Hoàng, Marcin Kamiński, Vadim Lozin, Joe Sawada, Xiao Shu, Deciding k-Colorability of P 5-Free Graphs in Polynomial Time Algorithmica. ,vol. 57, pp. 74- 81 ,(2010) , 10.1007/S00453-008-9197-8
Richard M. Karp, Reducibility Among Combinatorial Problems. Complexity of Computer Computations. pp. 85- 103 ,(1972)
Raffaele Mosca, Some results on stable sets for k-colorable P₆-free graphs and generalizations Discrete Mathematics & Theoretical Computer Science. ,vol. 14, pp. 37- 56 ,(2012)
Rodney G. Downey, M. R. Fellows, Parameterized Complexity ,(1998)
Barry Peyton, Jean R. S. Blair, An introduction to chordal graphs and clique trees Institute for Mathematics and Its Applications. ,vol. 56, pp. 1- ,(1993)
M.Komp, Adhi Harmoko S, Joseph Marie Jacquard, Eniac, Konrad Zuse, Introduction to Algorithms ,(2005)
University of California, Berkeley. Computer Science, Reducibility Among Combinatorial Problems ,(2012)