Vertex Cover in Graphs with Locally Few Colors
type: Item
instance of: scholarly article
title: Vertex Cover in Graphs with Locally Few Colors
zbMATH Open document ID: 1334.68089
DOI: 10.1007/978-3-642-22006-7_42
author: Fabian Kuhn
author: Monaldo Mastrolilli
published in: Automata, Languages and Programming
publication date: 2011-07-06T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 5917987
zbMATH Keywords: approximation
zbMATH Keywords: local coloring
zbMATH Keywords: scheduling
zbMATH Keywords: vertex cover
MaRDI profile type: Publication
OpenAlex ID: W136172668
cites work: Single machine precedence constrained scheduling is a Vertex cover problem
cites work: Scheduling with Precedence Constraints of Low Fractional Dimension
cites work: Approximating Precedence-Constrained Single Machine Scheduling by Coloring
cites work: Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
cites work: Q3002828
cites work: Optimal Long Code Test with One Free Bit
cites work: Fractional dimension of partial orders
cites work: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
cites work: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
cites work: Single-Machine Scheduling with Precedence Constraints
cites work: On the hardness of approximating minimum vertex cover
cites work: Partially Ordered Sets
cites work: Coloring graphs with locally few colors
cites work: On the fractional dimension of partially ordered sets
cites work: Dimension, graph and hypergraph coloring
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: A better approximation ratio for the vertex cover problem
cites work: Approximate graph coloring by semidefinite programming
cites work: On the power of unique 2-prover 1-round games
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
cites work: Local chromatic number and Sperner capacity
cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
cites work: Complexity of Scheduling under Precedence Constraints
cites work: Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
cites work: Vertex packings: Structural properties and algorithms
cites work: An algorithm for the single machine sequencing problem with precedence constraints
cites work: Polynomial time approximation algorithms for machine scheduling: Ten open problems
description: scientific article