Vertex Cover in Graphs with Locally Few Colors

DOI10.1007/978-3-642-22006-7_42zbMath1334.68089MaRDI QIDQ3012828

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.7696

zbMATH Keywords

scheduling; approximation; vertex cover; local coloring

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

68W20: Randomized algorithms

Cites Work

Unnamed Item
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
On the hardness of approximating minimum vertex cover
Single machine precedence constrained scheduling is a Vertex cover problem
Efficient bounds for the stable set, vertex cover and set packing problems
Coloring graphs with locally few colors
On the fractional dimension of partially ordered sets
Dimension, graph and hypergraph coloring
Fractional dimension of partial orders
Polynomial time approximation algorithms for machine scheduling: Ten open problems
Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Local chromatic number and Sperner capacity
A better approximation ratio for the vertex cover problem
Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
On the power of unique 2-prover 1-round games
Approximating Precedence-Constrained Single Machine Scheduling by Coloring
Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
Approximate graph coloring by semidefinite programming
An algorithm for the single machine sequencing problem with precedence constraints
Vertex packings: Structural properties and algorithms
Complexity of Scheduling under Precedence Constraints
Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
Optimal Long Code Test with One Free Bit
Single-Machine Scheduling with Precedence Constraints
Scheduling with Precedence Constraints of Low Fractional Dimension
Partially Ordered Sets