An improved branching algorithm for the proper interval edge deletion problem

Wenjun LI, Xiaojing TANG, Yongjie YANG

PDF(794 KB)
PDF(794 KB)
Front. Comput. Sci. ›› 2022, Vol. 16 ›› Issue (2) : 162401. DOI: 10.1007/s11704-020-0137-3
LETTER

An improved branching algorithm for the proper interval edge deletion problem

Author information +
History +

Graphical abstract

Cite this article

Download citation ▾
Wenjun LI, Xiaojing TANG, Yongjie YANG. An improved branching algorithm for the proper interval edge deletion problem. Front. Comput. Sci., 2022, 16(2): 162401 https://doi.org/10.1007/s11704-020-0137-3

References

[1]
Cai L . Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 1996, 58( 4): 171– 176
CrossRef Google scholar
[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
CrossRef Google scholar
[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
CrossRef Google scholar
[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]
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
CrossRef Google scholar
[8]
Cao Y . Unit interval editing is fixed-parameter tractable. Information and Computation, 2017, 253 : 109– 126
CrossRef Google scholar
[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
CrossRef Google scholar
[10]
Kleinberg J M, Tardos É. Algorithm design. Addison-Wesley, 2006

Acknowledgements

This paper was supported by the National Natural Science Foundation of China (Grant Nos. 61872048, 61972330, 61702557), the Natural Science Foundation of Hunan Province (Grant No. 2019JJ50453), and the Postgraduate Scientific Research Innovation Project of Hunan Province (CX20200883).

Supporting Information

The supporting information is available online at journal.hep.com.cn and link.springer.com.

RIGHTS & PERMISSIONS

2022 Higher Education Press
AI Summary AI Mindmap
PDF(794 KB)

Accesses

Citations

Detail

Sections
Recommended

/