Titlebook: Combinatorial Optimization and Applications; 10th International C T-H. Hubert Chan,Minming Li,Lusheng Wang Conference proceedings 2016 Spri

LIEN

Computing a Tree Having a Small Vertex Coverhard to achieve an .-approximation for the problem with general graphs. In this paper, we present constant-factor approximation algorithms for the problem with unit disk graphs and with graphs excluding a fixed minor.

停止偿付

On the Approximability of ,ed fixed-cardinality maximization problem . that aims at maximizing the number of equivalence classes induced by a solution set of . vertices. We study the approximation complexity of . on general hypergraphs and on more restricted instances, in particular, neighborhood hypergraphs of graphs.

我不怕牺牲

Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysishose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of . to this new variant, and we prove that unlike ., . is already hard on graphs at distance two from disjoint paths.

Insulin

Fast Searching on Complete ,-partite Graphsaphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs.

最低点

变量

Outmoded

John Hunt BSc, PhD, MBCS, C.Engand present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

厌倦吗你

Safe Sets in Graphs: Graph Classes and Structural Parametersand present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

Exposure

0302-9743 selected from 122 submissions. The papers are organized in topical sections such as graph theory, geometric optimization, complexity and data structure, combinatorial optimization, and miscellaneous..978-3-319-48748-9978-3-319-48749-6Series ISSN 0302-9743 Series E-ISSN 1611-3349

JOT

Smaller Satellites: Bigger Business?roximation algorithm, and an .-approximation algorithm by reducing it to ., where . is the approximation ratio for the . problem. More importantly, we show that . and . are in fact equivalent in approximability up to a factor of 2. We also prove a weak approximation hardness result for . under the assumption ..