An improved branching algorithm for the proper interval edge deletion problem

Graphical abstract

References

[1] Cai L . Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 1996, 58( 4): 171– 176

[2] Downey R G, Fellows M R. Parameterized computational feasibility. In: Proceedings of Feasible Mathematics Ⅱ, 1995, 219–244

[3] Gardi F . The Roberts characterization of proper and unit interval graphs. Discrete Mathematics, 2007, 307( 22): 2906– 2908

[4] Fomin F V , Saurabh S , Villanger Y . A polynomial kernel for proper interval vertex deletion. SIAM Journal of Discrete Mathematics, 2013, 27( 4): 1964– 1976

[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 ⁿ. PhD thesis, Göttingen, 1967.

[7] Goldberg P W , Golumbic M C , Kaplan H , Shamir R . Four strikes against physical mapping of DNA. Journal of Computational Biology, 1995, 2( 1): 139– 152

[8] Cao Y . Unit interval editing is fixed-parameter tractable. Information and Computation, 2017, 253 : 109– 126

[9] Liu Y , Wang J , Xu C , Guo J , Chen J . An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs. Journal of Combinatorial and Optimization, 2015, 29( 1): 257– 275

[10] Kleinberg J M, Tardos É. Algorithm design. Addison-Wesley, 2006

RIGHTS & PERMISSIONS

Higher Education Press