Read more
This two-volume set, LNCS 15983 and 15984, constitutes the referred proceedings of the 31st International Computing and Combinatorics Conference, COCOON 2025, held in Chengdu, China, during August 15 17, 2025.
The 54 full papers were carefully reviewed and selected from 191 submissions. COCOON 2025 provided an excellent venue for researchers working in the topical sections as follows:
Part I: Approximation Algorithms, Combinatorial Optimization, Computational Complexity, Computational Geometry, Economics and Computation.
Part II: Graph Algorithms and Graph Theory, Learning and Data-Related Theory, Parameterized Algorithms, String Algorithms and Discrete Structures.
List of contents
.- Graph Algorithms and Graph Theory.
.- On the Complexity of 2-Club Cluster Editing with Vertex Splitting.
.- A sufficient condition for the existence of two completely independent spanning trees.
.- Undecidability of polynomial inequalities in subset densities and additive energies.
.- Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints.
.- Sum-of-Max Chain Partition of a Tree.
.- Reconfiguring Multiple Connected Components with Size Multiset Constraints.
.- Fault diagnosability evaluation of BCCC data center networks.
.- Testing Some First-Order Logic Properties on Sparse Graphs.
.- Massively Parallel Approximate Steiner Tree Algorithms.
.- A Multi-start Variable Neighborhood Tabu Search Algorithm for the Cyclic Bandwidth Problem.
.- Vertex-Critical (P5, W4)-Free Graphs.
.- Learning and Data-Related Theory.
.- A Dynamic Working Set Method for Compressed Sensing.
.- Data Debugging is NP-hard for Classifiers Trained with SGD.
.- Coresets for k-Median of Lines with Group Fairness Constraints.
.- Redefining Entity Integration: Theoretical Insights for GNN-based Recommender Systems.
.- Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits.
.- A Robust Distributed Minimax Learning Method against Model Poisoning Attacks.
.- Parameterized Algorithms.
.- Parameterized Complexity of Influence Maximization.
.- Improved Parameterized Algorithms for Scheduling with Precedence Constraints and Time Windows.
.- Pareto Optimal Matching with Multilayer Preferences: How Hard Can It Be?.
.- An FPT Factor-11 Approximation Algorithm for TSP.
.- From Metric to General Graphs: FPT Constant-Factor Approximation Algorithms for Three Location Problems.
.- String Algorithms and Discrete Structures.
.- Revisit the Partial Coloring Method: Prefix Spencer and Sampling.
.- A Sparse Dynamic Programming Algorithm for Solving the Coding Sequence Design Problem.
.- Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals.
.- Longest Double-Bounded (k]-tuple Common Substrings.
.- Finding cycle types in permutation groups with few generators.
.- Counting overlapping pairs of words.
