Greed is good: Approximating independent sets in sparse and bounded-degree graphs
From MaRDI portal
Publication:679458
DOI10.1007/BF02523693zbMath0866.68077WikidataQ56335611 ScholiaQ56335611MaRDI QIDQ679458
Magnús M. Halldórsson, Jaikumar Radhakrishnan
Publication date: 20 July 1997
Published in: Algorithmica (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)
Related Items (41)
Verified Approximation Algorithms ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Filtering algorithms for the NValue constraint ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Explore and repair graphs with black holes using mobile entities ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Computing convex quadrangulations ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ A Modern View on Stability of Approximation ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem ⋮ Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections ⋮ Recoverable Values for Independent Sets ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Minimum entropy combinatorial optimization problems ⋮ New potential functions for greedy independence and coloring ⋮ Bounding the feedback vertex number of digraphs in terms of vertex degrees ⋮ On the maximum edge-pair embedding bipartite matching ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs ⋮ Unnamed Item ⋮ Simple and local independent set approximation ⋮ Generalizing Geometric Graphs ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Approximability of open \(k\)-monopoly problems ⋮ Independent sets in bounded-degree hypergraphs ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ Combinatorial properties of Farey graphs ⋮ A Generalization of Spatial Monte Carlo Integration ⋮ Solving maximum independent set by asynchronous distributed hopfield-type neural networks ⋮ A note on greedy algorithms for the maximum weighted independent set problem ⋮ A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the independence number of triangle-free graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- Optimization, approximation, and complexity classes
- Small transversals in hypergraphs
- Three short proofs in graph theory
- Lower bounds on the independence number in terms of the degrees
- Derandomized graph products
- On Approximate Solutions for Combinatorial Optimization Problems
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- Vertex packings: Structural properties and algorithms
- On Syntactic versus Computational Views of Approximability
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
