An improved branching algorithm for the proper interval edge deletion problem
Wenjun LI1, Xiaojing TANG1, Yongjie YANG2()
1. School of Computer and Communication Engineering, Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha 410015, China 2. School of Computer Science and Engineering, Central South University, Changsha 410083, China
L Cai . Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 1996, 58( 4): 171– 176 https://doi.org/10.1016/0020-0190(96)00050-6
2
Downey R G, Fellows M R. Parameterized computational feasibility. In: Proceedings of Feasible Mathematics Ⅱ, 1995, 219–244
F V Fomin , S Saurabh , Y Villanger . A polynomial kernel for proper interval vertex deletion. SIAM Journal of Discrete Mathematics, 2013, 27( 4): 1964– 1976 https://doi.org/10.1137/12089051X
5
Brandstädt A, Le V B, Spinrad J P. Graph Classes: A Survey. Society for Industrial and Applied Mathematics, 1999
6
Wegner G. Eigenschaften der Nerven HomologischEinfacher Familien im R n. PhD thesis, Göttingen, 1967.
7
P W Goldberg , M C Golumbic , H Kaplan , R Shamir . Four strikes against physical mapping of DNA. Journal of Computational Biology, 1995, 2( 1): 139– 152 https://doi.org/10.1089/cmb.1995.2.139
Y Liu , J Wang , C Xu , J Guo , J Chen . An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs. Journal of Combinatorial and Optimization, 2015, 29( 1): 257– 275 https://doi.org/10.1007/s10878-014-9733-1
10
Kleinberg J M, Tardos É. Algorithm design. Addison-Wesley, 2006
