Computing and Combinatorics
Description
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.
More details
Other editions
Additional editions
Content
.- 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.