Vertex Cover in Graphs with Locally Few Colors
DOI10.1007/978-3-642-22006-7_42zbMath1334.68089OpenAlexW136172668MaRDI QIDQ3012828
Fabian Kuhn, Monaldo Mastrolilli
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
Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (3)
Cites Work
- Unnamed Item
- 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
- 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
This page was built for publication: Vertex Cover in Graphs with Locally Few Colors
