Termination of Multipartite Graph Series Arising from Complex Network Modelling -- Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids -- Evacuation of Rectilinear Polygons -- A Fast Algorithm for Powerful Alliances in Trees -- NP-Completeness of Spreading Colored Points -- Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach -- Feasibility-Based Bounds Tightening via Fixed Points -- A Characterisation of Stable Sets in Games with Transitive Preference -- Linear Coherent Bi-cluster Discovery via Beam Detection and Sample Set Clustering -- An Iterative Algorithm of Computing the Transitive Closure of a Union of Parameterized Affine Integer Tuple Relations -- Bases of Primitive Nonpowerful Sign Patterns -- Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures -- Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets -- Finding Strong Bridges and Strong Articulation Points in Linear Time -- Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks -- An Efficient Algorithm for Chinese Postman Walk on Bi-directed de Bruijn Graphs -- On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs -- Cyclic Vertex Connectivity of Star Graphs -- The Number of Shortest Paths in the (n, k)-Star Graphs -- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems -- PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks -- A Primal-Dual Approximation Algorithm for the Asymmetric Prize-Collecting TSP -- Computing Toolpaths for 5-Axis NC Machines -- A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs -- A Randomized Algorithm for Weighted Approximation of Points by a Step Function -- Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials -- The Union of Colorful Simplices Spanned by a Colored Point Set -- Compact Visibility Representation of 4-Connected Plane Graphs -- Some Variations on Constrained Minimum Enclosing Circle Problem -- Searching for an Axis-Parallel Shoreline -- Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs -- Scheduling Packets with Values and Deadlines in Size-Bounded Buffers -- Transporting Jobs through a Processing Center with Two Parallel Machines.

This book constitutes the refereed proceedings of the 4th International Conference on Combinatorial Optimization and Applications, COCOA 2010, held in Kailua-Kona, HI, USA, in December 2010. The 49 revised full papers were carefully reviewed and selected from 108 submissions.