Publications of Yixin Cao

Books and Edited Special Issues of Journals

Computing and Combinatorics, Yixin Cao and Jianer Chen, editors. Lecture Notes in Computer Science vol. 10392, Springer (2017) [publisher]

Journal Articles

Unit interval editing is fixed-parameter tractable. Information and Computation, 253(1):109–126 (2017) [publisher]

Approximate association via dissociation, with Jianxin Wang and Jie You. Discrete Applied Mathematics, 219:202–209 (2017) [publisher]

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, with Jianer Chen, Wenjun Li, and Jianxin Wang. Information and Computation, 252:187–200 (2017) [publisher]

Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection, with Luciano N. Grippo and Martin D. Safe. Discrete Applied Mathematics, 216(1):67–83 (2017) [publisher]

Chordal editing is fixed-parameter tractable, with Dániel Marx. Algorithmica, 75(1):118–137 (2016) [publisher]

On feedback vertex set: New measure and new structures, with Jianer Chen and Yang Liu. Algorithmica, 73(1):63–86 (2015) [publisher]

Edge deletion problems: Branching facilitated by modular decomposition, with Jianer Chen, Yunlong Liu, Jianxin Wang, and Jie You. Theoretical Computer Science, 573:63–70 (2015) [publisher]

Interval deletion is fixed-parameter tractable, with Dániel Marx. ACM Transactions on Algorithms, 11(3), Article 21 (2015) [publisher]

An O*(1.84k) parameterized algorithm for the multiterminal cut problem, with Jianer Chen and Jia-Hao Fan. Information Processing Letters, 114(4): 167–173 (2014) [publisher]

Cluster editing: Kernelization based on edge cuts, with Jianer Chen. Algorithmica, 64(1): 152–169 (2012) [publisher]

Referred Conference Papers

A naive algorithm for feedback vertex set. Proceedings of the first Symposium on Simplicity in Algorithms (SOSA 2018), to appear. [arxiv][publisher]

Vertex deletion problems on chordal graphs, with Yuping Ke, Yota Otachi, and Jie You. Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), to appear. [arxiv][publisher]

Minimum fill-in: Inapproximability and almost tight lower bounds, with R. B. Sandeep. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 875–880. [arxiv][publisher]

Approximate association via dissociation, with Jianxin Wang and Jie You. Proceedings of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), LNCS vol. 9941, pp. 13–24. [arxiv][publisher]

Linear recognition of almost interval graphs. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 1096–1115. [arxiv (to be updated soon)][publisher]

A 2k-vertex kernel for maximum internal spanning tree, with Jianer Chen, Wenjun Li, and Jianxin Wang. Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), LNCS vol. 9214, pp. 495–505. [arxiv][publisher]

Unit interval editing is fixed-parameter tractable. Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), LNCS vol. 9134, pp. 306–317. [arxiv][publisher]

Direct and certifying recognition of normal Helly circular-arc graphs in linear time. Proceedings of the 8th International Frontiers of Algorithmics Workshop (FAW 2014), LNCS vol. 8497, pp. 13–24. [arxiv] [publisher]

The (un)supervised detection of overlapping communities as well as hubs and outliers via (Bayesian) NMF, with Xiaochun Cao, Xiao Wang, Di Jin, and Dongxiao He. Proceedings of the companion publication of the 23rd international conference on World wide web companion (WWW Companion 2014), pp. 233-234. [publisher]

Chordal editing is fixed-parameter tractable, with Dániel Marx. Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 214–225. [arxiv][publisher]

Interval deletion is fixed-parameter tractable, with Dániel Marx. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pp. 122–141. [arxiv][publisher]

An O*(1.84k) parameterized algorithm for the multiterminal cut problem, with Jianer Chen and Jia-Hao Fan. Proceedings of the 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), LNCS vol. 8070, pp. 84–94. [pdf][publisher]

On parameterized and kernelization algorithms for the hierarchical clustering problem, with Jianer Chen. Proceedings of the 10th International Conference on Theory and Applications of Models of Computation (TAMC 2013), LNCS vol. 7876, pp. 319–330. [pdf][publisher]

Cluster editing: Kernelization based on edge cuts, with Jianer Chen. Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC 2010), LNCS vol. 6478, pp. 60–71. [arxiv] [publisher]

On feedback vertex set: New measure and new structures, with Jianer Chen and Yang Liu. Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), LNCS vol. 6139, pp. 93–104. [arxiv] [publisher]

Computing with unknowns in computer algebra systems, with Gabriel Dos Reis. Proceedings of Programming Languages for Mechanized Mathematics (PLMMS), Birmingham, UK, 29 July 2008. pp. 4–17.

Manuscripts under Preparation or Submission

Unit interval vertex deletion: Fewer vertices are relevant, with Yuping Ke, Xiating Ouyang, and Jianxin Wang. Submitted. [arxiv]

A survey of feedback set problems. In progress.

Other Technical Writings

Review of flows in networks by L. R. Ford Jr. and D. R. Fulkerson. ACM SIGACT News, 44(2): 28-30 (2013) [publisher]

Last updated: November 10, 2017.