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