Publications
I recommend DBLP for the list of publications since I may not update this list regularly.
2024
[19] Mingyu Xiao. Solving Directed Multiway Cut Faster Than 2^n. ESA 2024 (accepted)
[18] Jingyang Zhao, Mingyu Xiao. A Deterministic Approximation Algorithm for Metric Triangle Packing. Theoretical Computer Science (accepted)
[17] Zimo Sheng, Mingyu Xiao. A linear vertex kernel for the paw edge covering problem (In Chinese). SCIENTIA SINICA Informationis (accepted)
[16] Ziliang Xiong, Yi Zhou, Mingyu Xiao, Bakhadyr Khoussainov. Finding small feedback arc sets on large graphs. Computers & Operations Research (accepted)
[15] Mengfan Ma, Mingyu Xiao, Tian Bai, Xin Cheng. Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism Design. COCOON 2024 (accepted)
[14] Kangyi Tian, Mingyu Xiao, Haotian Pan. A Quadratic Vertex Kernel for Diamond-free Edge Deletion. COCOON 2024 (accepted)
[13] Junqiang Peng, Mingyu Xiao: A Fast Algorithm for MaxSAT Above Half Number of Clauses. IJCAI 2024 (accepted)
[12] Jingyang Zhao, Mingyu Xiao, Shunwang Wang: Improved Approximation Algorithms for Capacitated Location Routing. IJCAI 2024 (accepted)
[11] Jingyang Zhao, Mingyu Xiao: A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling. IJCAI 2024 (accepted)
[10] Ziliang Xiong, Mingyu Xiao: Exactly Solving Minimum Dominating Set and its Generalization. IJCAI 2024 (accepted)
[9] Jingyang Zhao, Mingyu Xiao: An Improved Approximation Algorithm for Metric Triangle Packing. TAMC 2024: 50-62
[8] Yuxi Liu, Mingyu Xiao: An Improved Kernel and Parameterized Algorithm for Almost Induced Matching. TAMC 2024: 86-98
[7] Jingyang Zhao, Mingyu Xiao: Practical Algorithms with Guaranteed Approximation Ratio for TTP with Maximum Tour Length Two. Mathematics of Operations Research 2024 (accepted)
[6] Yuhang Guo, Ddong Hao, Mingyu Xiao and Bin Li: Networked Combinatorial Auction for Crowdsourcing and Crowdsensing. IEEE Internet of Things Journal 11(4): 5951-5966 (2024)
[5] Mingyu Xiao, Shen Huang, and Xiaoyu Chen: Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs. Algorithmica 86(5): 1293-1334 (2024)
[4] Lu Liu, Mingyu Xiao, and Yi Zhou: A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem. AAAI 2024: 20768-20776
[3] Zimo Sheng, Mingyu Xiao: Kernelization for Edge Triangle Packing and Covering via a Discharging Method. Theoretical Computer Science 1004: 114635 (2024)
[2] Tian Bai, Mingyu Xiao: Exact algorithms for restricted subset feedback vertex set in chordal and split graphs. Theoretical Computer Science 984: 114326 (2024)
[1] Jingyang Zhao, Mingyu Xiao: Improved Approximation Algorithms for Cycle and Path Packings, WALCOM 2024: 179-193
2023
[19] Junqiang Peng, Mingyu Xiao: Further improvements for SAT in terms of formula length. Information and Computation 294: 105085 (2023)
[18] Kangyi Tian, Mingyu Xiao, Boting Yang: An Improved Parameterized Algorithm for Cluster Vertex Deletion. COCOON 2023: 182-194.
[17] Zimo Sheng, Mingyu Xiao: A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering. COCOON 2023:171-183.
[16] Jingyang Zhao, Mingyu Xiao: Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing. COCOON 2023: 378-391. (Best Paper Award)
[15] Zihui Liang, Bakh Khoussainov, Toru Takisaka, Mingyu Xiao: Connectivity in the presence of an opponent. ESA, 2023: 79:1-79:14
[14] Binglin Tao; Mingyu Xiao; Jingyang Zhao: Minimum-Weight Link-Disjoint Paths with a Bounded Number of Shared Nodes. IEEE Transactions on Network and Service Management, 20(3): 2598-2610 (2023)
[13] Zhengren Wang, Zhou Yi, Chunyu Luo, Mingyu Xiao: A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap. IJCAI 2023: 5648-5656
[12] Junqiang Peng, Mingyu Xiao: Fast Algorithms for SAT with Bounded Occurrences of Variables. IJCAI 2023: 2004-2012
[11] Yuan Fang, Mengxiao Zhang, Jiamou Liu, Bakh Khoussainov, Mingyu Xiao: Multi-unit Auction over a Social Network. ECAI 2023: 676-683
[10] Mingyu Xiao, Guixin Lin, Bakh Khoussainov, Yuchao Song: Characterizations of Network Auctions and Generalizations of VCG. ECAI 2023: 2736-2743
[9] Mengfan Ma, Ziyang Men, André Rossi, Yi Zhou, Mingyu Xiao: A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem. Comput. Oper. Res. 153: 106151 (2023)
[8] Yuhao Liu, Mingyu Xiao: The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles. Discret. Math. 346(4): 113306 (2023)
[7] Shan Hu, Yi Zhou, Mingyu Xiao, Zhang-Hua Fu, Zhipeng Lü: Listing maximal k-relaxed-vertex connected components from large graphs. Inf. Sci. 620: 67-83 (2023)
[6] Mingyu Xiao: Upper and lower bounds on approximating weighted mixed domination. Theor. Comput. Sci. 939: 292-302 (2023)
[5] Mingyu Xiao, Shaowei Kou: A 5k-vertex kernel for 3-path vertex cover. Theor. Comput. Sci. 959: 113872 (2023)
[4] Tian Bai, Mingyu Xiao: A parameterized algorithm for subset feedback vertex set in tournaments. Theor. Comput. Sci. 975: 114139 (2023)
[3] Mengfan Ma, Mingyu Xiao, Tian Bai, Bakh Khoussainov: Facility Location Games with Entrance Fees. AAAI 2023: 5797-5804
[2] Jingyang Zhao, Mingyu Xiao: The Linear Distance Traveling Tournament Problem Allows an EPTAS. AAAI 2023: 12155-12162
[1] Mingyu Xiao, Guoliang Qiu, Sen Huang: MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results. AAMAS 2023: 2886-2888
2022
[11] Ton Kloks, Mingyu Xiao: A Guide to Graph Algorithms. Springer 2022, ISBN 978-981-16-6349-9, pp. 1-340
[10] Yi Zhou, Weibo Lin, Jin-Kao Hao, Mingyu Xiao, Yan Jin: An effective branch-and-bound algorithm for the maximum s-bundle problem. Eur. J. Oper. Res. 297(1): 27-39 (2022)
[9] Mingyu Xiao, Shaowei Kou: A simple and improved parameterized algorithm for bicluster editing. Inf. Process. Lett. 174: 106193 (2022)
[8] Mingyu Xiao, Jianan Zhang, Weibo Lin: Parameterized algorithms and complexity for the traveling purchaser problem and its variants. J. Comb. Optim. 44(4): 2269-2285 (2022)
[7] Zimo Sheng, Mingyu Xiao: An improved kernel for planar vertex-disjoint triangle packing. Theor. Comput. Sci. 922: 122-130 (2022)
[6] Mingyu Xiao, Yuchao Song, Bakh Khoussainov: Multi-Unit Auction in Social Networks with Budgets. AAAI 2022: 5228-5235
[5] Mingyu Xiao: An Exact MaxSAT Algorithm: Further Observations and Further Improvements. IJCAI 2022: 1887-1893
[4] Binglin Tao, Mingyu Xiao, Bakhadyr Khoussainov, Junqiang Peng: Optimal Shielding to Guarantee Region-Based Connectivity under Geographical Failures. INFOCOM 2022: 1109-1118
[3] Jingyang Zhao, Mingyu Xiao, Chao Xu: Improved Approximation Algorithms for the Traveling Tournament Problem. MFCS 2022: 83:1-83:15
[2] Tian Bai, Mingyu Xiao: Exact and Parameterized Algorithms for Restricted Subset Feedback Vertex Set in Chordal Graphs. TAMC 2022: 249-261
[1] Zhengren Wang, Yi Zhou, Mingyu Xiao, Bakhadyr Khoussainov: Listing Maximal k-Plexes in Large Real-World Graphs. WWW 2022: 1517-1527
2021
[10] Xiaoyu Chen, Yi Zhou, Jin-Kao Hao, Mingyu Xiao: Computing maximum k-defective cliques in massive graphs. Comput. Oper. Res. 127: 105131 (2021)
[9] Huairui Chu, Mingyu Xiao, Zhe Zhang: An improved upper bound for SAT. Theor. Comput. Sci. 887: 51-62 (2021)
[8] Huairui Chu, Mingyu Xiao, Zhe Zhang: An Improved Upper Bound for SAT. AAAI 2021: 3707-3714
[7] Zhenyu Guo, Mingyu Xiao, Yi Zhou, Dongxiang Zhang, Kian-Lee Tan: Enhancing Balanced Graph Edge Partition with Effective Local Search. AAAI 2021: 12336-12343
[6] Yi Zhou, Shan Hu, Mingyu Xiao, Zhang-Hua Fu: Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding. AAAI 2021: 12453-12460
[5] Jingyang Zhao, Mingyu Xiao: A Further Improvement on Approximating TTP-2. COCOON 2021: 137-149
[4] Sen Huang, Mingyu Xiao, Xiaoyu Chen: Exact Algorithms for Maximum Weighted Independent Set on Sparse Graphs (Extended Abstract). COCOON 2021: 617-628
[3] Jingyang Zhao, Mingyu Xiao: The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound. IJCAI 2021: 4206-4212
[2] Junqiang Peng, Mingyu Xiao: A Fast Algorithm for SAT in Terms of Formula Length. SAT 2021: 436-452
[1] Mingyu Xiao, Sen Huang, Yi Zhou, Bolin Ding: Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set. WWW 2021: 3930-3940
2020
[11] Sen Huang, Mingyu Xiao: Object reachability via swaps under strict and weak preferences. Auton. Agents Multi Agent Syst. 34(2): 51 (2020)
[10] Mingyu Xiao, Hiroshi Nagamochi: Characterizing Star-PCGs. Algorithmica 82(10): 3066-3090 (2020)
[9] Mingyu Xiao, Hiroshi Nagamochi: Some reduction operations to pairwise compatibility graphs. Inf. Process. Lett. 153 (2020)
[8] Qiuxia Lai, Yongwei Nie, Hanqiu Sun, Qiang Xu, Zhensong Zhang, Mingyu Xiao: Video super-resolution via pre-frame constrained and deep-feature enhanced sparse reconstruction. Pattern Recognit. 100: 107139 (2020)
[7] Mingyu Xiao, Zimo Sheng: Improved parameterized algorithms and kernels for mixed domination. Theor. Comput. Sci. 815: 109-120 (2020)
[6] Mingyu Xiao, Shaowei Kou: Parameterized algorithms and kernels for almost induced matching. Theor. Comput. Sci. 846: 103-113 (2020)
[5] Zhensong Zhang, Yongwei Nie, Hanqiu Sun, Qing Zhang, Qiuxia Lai, Guiqing Li, Mingyu Xiao: Multi-View Video Synopsis via Simultaneous Object-Shifting and View-Switching Optimization. IEEE Trans. Image Process. 29: 971-985 (2020)
[4] Binglin Tao, Mingyu Xiao, Jingyang Zhao: Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes. AAAI 2020: 938-945
[3] Mingyu Xiao, Jiaxing Ling: Algorithms for Manipulating Sequential Allocation. AAAI 2020: 2302-2309
[2] Yi Zhou, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, Yan Jin: Enumerating Maximal k-Plexes with Worst-Case Time Guarantee. AAAI 2020: 2442-2449
[1] Zhenyu Guo, Mingyu Xiao, Yi Zhou: The Complexity of the Partition Coloring Problem. TAMC 2020: 390-401
2019
[8] Weibo Lin, Mingyu Xiao, Yi Zhou, Zhenyu Guo: Computing lower bounds for minimum sum coloring and optimum cost chromatic partition. Comput. Oper. Res. 109: 263-272 (2019)
[7] Weibo Lin, Mingyu Xiao: A (3 + ϵ)k-vertex kernel for edge-disjoint triangle packing. Inf. Process. Lett. 142: 20-26 (2019)
[6] Mingyu Xiao, Frances A. Rosamond: Frontiers in Algorithmics. Theor. Comput. Sci. 786: 1 (2019)
[5] Sen Huang, Mingyu Xiao: Object Reachability via Swaps along a Line. AAAI 2019: 2037-2044
[4] Mingyu Xiao, Zimo Sheng: Improved Parameterized Algorithms for Mixed Domination. AAIM 2019: 304-315
[3] Mingyu Xiao: Upper and Lower Bounds on Approximating Weighted Mixed Domination. COCOON 2019: 554-566
[2] Mingyu Xiao, Jianan Zhang, Weibo Lin: Parameterized Algorithms for the Traveling Purchaser Problem with Additional Constraints. COCOON 2019: 567-579
[1] Weibo Lin, Zhu He, Mingyu Xiao: Balanced Clustering: A Uniform Model and Fast Algorithm. IJCAI 2019: 2987-2993
2018
[4] Mingyu Xiao, Yuqing Wang, Binglin Tao: A Geometric Least Squares Method for Peer Assessment. AAMAS 2018: 2124-2126
[3] Mingyu Xiao, Hiroshi Nagamochi: Characterizing Star-PCGs. COCOON 2018: 504-515
[2] Mingyu Xiao, Hiroshi Nagamochi: Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable. ICALP 2018: 112:1-112:6
[1] Mingyu Xiao, Xuanbei Wang: Exact Algorithms and Complexity of Kidney Exchange. IJCAI 2018: 555-561
Before 2017
Journal
24. M. Xiao and H.Nagamochi. Exact Algorithms for Maximum Independent Set. Information and Computation 255:126-146 (2017) (A previous version with a weaker result appeared In: ISAAC 2013)
23. M. Xiao and H.Tan. Exact Algorithms for Maximum Induced Matching. Information and Computation 256: 196-211 (2017)
22. M. Xiao. Linear kernels for separating a graph into components of bounded size. Journal of Computer and System Sciences 88: 260-270 (2017)
21. M. Xiao. On a generalization of Nemhauser and Trotter's local optimization theorem. Journal of Computer and System Sciences 84: 97-106 (2017) (A previous version appeared in ISAAC 2015; PPT presented on ISAAC 2015 can be found here).
20. M. Xiao and S.Kou. Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theoretical Computer Science 657(A): 86-97 (2017) doi:10.1016/j.tcs.2016.04.043
19. M. Xiao and H.Nagamochi. Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs. Theoretical Computer Science 659:72-82 (2017) (A previous version appeared In: ISAAC 2014)
18. M. Xiao and H.Nagamochi. A refined algorithm for maximum independent set in degree-4 graphs. Journal of Combinatorial Optimization (2017) https://doi.org/10.1007/s10878-017-0115-3
17. M. Xiao and H. Nagamochi. An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs. Discrete Applied Mathematics 199:137-155 (2016)
16. M. Xiao and H. Nagamochi. An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4. Theory of Computing Systems. 58(2): 241-272 (2016) (A previous version with a weaker result appeared in COCOON 2012)
15. M. Xiao and H.Nagamochi. An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure. Algorithmica 74(2): 713-741 (2016)
14. M. Xiao and H.Nagamochi. An improved exact algorithm for undirected feedback vertex set. Journal of Combinatorial Optimization 30(2): 214-241 (2015) (A previous version with a weaker result appeared in COCOA 2013)
13. B. Escoffier, J. Monnot, V.Th. Paschos and M. Xiao. New results on polynomial inapproximability and fixed parameter approximability of EDGE DOMINATING SET.Theory of Computing Systems 56: 330-346 (2015)
12. M. Xiao and J.Guo. A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments. Algorithmica 71:87-97 (2015) (A previous version appeared in MFCS2012)
11. M. Xiao and H. Nagamochi. Exact Algorithms for Dominating Induced Matching Based on Graph Partition. Discrete Applied Mathematics 190-191: 147-162 (2015)
10. M. Xiao and H. Nagamochi. A Refined Exact Algorithm for Edge Dominating Set. Theoretical Computer Science 560:207-216 (2014)
9. M. Xiao, T. Kloks and S-H. Poon: New Parameterized Algorithms for the Edge Dominating Set Problem, Theoretical Computer Science 511:147-158 (2013) (A previous version appeared in MFCS2011)
8. M. Xiao and H. Nagamochi: Parameterized edge dominating set in graphs with degree bounded by 3, Theoretical Computer Science 508:2-15 (2013)
7. M. Xiao and H. Nagamochi. Exact Algorithms for Annotated Edge Dominating Set in Cubic Graphs. IEICE Transactions on Information and Systems 96-D(3): 408-418 (2013) (A previous version with a weaker result appeared in COCOA 2010)
6. M. Xiao, T. Fukunage and H. Nagamochi. FPTAS’s for Trimming Weighted Trees. Theoretical Computer Science 469: 105-118 (2013)
5. M. Xiao and H. Nagamochi. Confining Sets and Avoiding Bottleneck Cases: A Simple Maximum Independent Set Algorithm in Degree-3 Graphs. Theoretical Computer Science 469: 92-104 (2013)
4. M. Xiao and H. Nagamochi. An FPT Algorithm for Edge Subset Feedback Edge Set. Information Processing Letters 112(1-2): 5-9 (2012)
3. M. Xiao, L. Cai and A. Yao. Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut. Algorithmica. 59: //510–520 (2011)
2. M. Xiao. Simple and Improved Parameterized Algorithms for Multiterminal Cuts. Theory of Computing Systems, 46: 723–736 (2010) (A previous version appeared in CSR 2008)
1. M. Xiao. Finding Minimum 3-Way Cuts in Hypergraphs. Information Processing Letters,110: 554–558 (2010)
Conference
14. M. Xiao, Y. Wang. Score Aggregation via Spectral Method. In IJCAI 2017:451-457 (2017)
13. M. Xiao, W. Li, Y Dai and Y. Zeng. A Fast Algorithm to Compute Maximum k-Plexes in Social Network Analysis. In AAAI 2017: 919-925 (2017)
12. M. Xiao and S.Kou. Kernelization and Parameterized Algorithms for 3-Path Vertex Cover. In: TAMC 2017, LNCS 10185, pp 654-668, (2017)
11. M. Xiao and H.Nagamochi. A Linear-time Algorithm for Integral Multiterminal Flows in Trees. In: 27th International Symposium on Algorithms and Computation (ISAAC 2016). Editor: Seok-Hee Hong. LIPIcs 64, pp. 62:1--62:12 (2016) PPT presented on ISAAC 2016 can be found here
10. M. Xiao and S.Kou. An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Editors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier. LIPIcs 58, pp. 89:1–89:14 (2016) PPT presented on MFCS 2016 can be found here.
9. M. Xiao and S.Kou. Almost Induced Matching: Linear Kernels and Parameterized Algorithms. In: WG 2016 (2016)
8. M. Xiao. A Parameterized Algorithm for Bounded-Degree Vertex Deletion. In: COCOON 2016, LNCS 9797, pp. 79-91, (2016)
7. M. Xiao and H.Tan. An Improved Exact Algorithm for Maximum Induced Matching. In: R. Jain et al. (Eds.): TAMC 2015, LNCS 9076, pp. 1-12 (2015)
6. H. Jiang, B. Su, M. Xiao, Y. Xu, F. Zhong, B. Zhu: On the Exact Block Cover Problem. In: Q. Gu, P. Hell, and B. Yang (Eds.): AAIM 2014, LNCS 8546, pp. 13-22, 2014
5. M. Xiao. A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and Simpler. In: Q. Gu, P. Hell, and B. Yang (Eds.): AAIM 2014, LNCS 8546, pp. 288–298, 2014.
4. M. Xiao and H. Nagamochi. Further Improvement on Maximum Independent Set in Degree-4 Graphs. In W. Wang, X. Zhu, and D.-Z. Du (Eds.): COCOA 2011, LNCS 6831, pp. 163–178, 2011.
3. M. Xiao. A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs, In: Md.S.Rahman and S.Fujita(Eds.):WALCOM 2010. LNCS 5942, 281-292, 2010
2. M. Xiao. A Note on Vertex Cover in Graphs with Maximum Degree 3. In Thai, M.T., Sahni, S., eds.: COCOON. LNCS 6196, 150-159, 2010
1. M. Xiao. An Improved Divide-and-Conquer Algorithm for Finding all Minimum k-Way Cuts. In the proceeding of the 19th international symposium on algorithms and computation (ISAAC 2008). LNCS 5308, 147-158, 2008