Greed is good: Approximating independent sets in sparse and bounded-degree graphs
From MaRDI portal
(Redirected from Publication:679458)
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
Cites work
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 1003268 (Why is no real title available?)
- scientific article; zbMATH DE number 4101221 (Why is no real title available?)
- scientific article; zbMATH DE number 3482375 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- scientific article; zbMATH DE number 753971 (Why is no real title available?)
- A note on the independence number of triangle-free graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Derandomized graph products
- Efficient bounds for the stable set, vertex cover and set packing problems
- Locality in Distributed Graph Algorithms
- Lower bounds on the independence number in terms of the degrees
- On Approximate Solutions for Combinatorial Optimization Problems
- On Syntactic versus Computational Views of Approximability
- Optimization, approximation, and complexity classes
- Parallel Symmetry-Breaking in Sparse Graphs
- Small transversals in hypergraphs
- Three short proofs in graph theory
- Vertex packings: Structural properties and algorithms
Cited in
(53)- Greed is good: approximating independent sets in sparse and bounded-degree graphs
- On approximating minimum vertex cover for graphs with perfect matching
- A branch-price-and-cut algorithm for packing cuts in undirected graphs
- A generalization of spatial Monte Carlo integration
- The complexity of dissociation set problems in graphs
- Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
- Solving maximum independent set by asynchronous distributed hopfield-type neural networks
- Analysis of greedy algorithms on graphs with bounded degrees
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Ultimate greedy approximation of independent sets in subcubic graphs
- Verified Approximation Algorithms
- Explore and repair graphs with black holes using mobile entities
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- It is hard to know when greedy is good for finding independent sets
- Ultimate greedy approximation of independent sets in subcubic graphs
- A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
- On linear and semidefinite programming relaxations for hypergraph matching
- A Modern View on Stability of Approximation
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
- GreedyMAX-type algorithms for the maximum independent set problem
- Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
- On the maximum edge-pair embedding bipartite matching
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
- Computing convex quadrangulations
- Brief announcement: Simple and local independent set approximation
- A note on greedy algorithms for the maximum weighted independent set problem
- Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem
- Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
- New potential functions for greedy independence and coloring
- Filtering algorithms for the NValue constraint
- scientific article; zbMATH DE number 1405697 (Why is no real title available?)
- Greedy approximations of independent sets in low degree graphs
- Vertex cover in graphs with locally few colors
- Improved (In-)Approximability Bounds for d-Scattered Set
- Greedy heuristic guided by lexicographic excellence
- scientific article; zbMATH DE number 20942 (Why is no real title available?)
- Independent sets in bounded-degree hypergraphs
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- Simple and local independent set approximation
- Minimum entropy combinatorial optimization problems
- Improved approximations of independent sets in bounded-degree graphs
- A survey on combinatorial optimization in dynamic environments
- Generalizing geometric graphs
- The greedier the better: an efficient algorithm for approximating maximum independent set
- An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
- On the complexity of the independent set problem in triangle graphs
- Combinatorial properties of Farey graphs
- scientific article; zbMATH DE number 7566049 (Why is no real title available?)
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Maximum 0-1 timed matching on temporal graphs
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
- Approximability of open \(k\)-monopoly problems
- Bounding the feedback vertex number of digraphs in terms of vertex degrees
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)
