A note on greedy algorithms for the maximum weighted independent set problem
From MaRDI portal
Publication:1861582
DOI10.1016/S0166-218X(02)00205-6zbMath1013.90108MaRDI QIDQ1861582
Mitsunori Togasaki, Koichi Yamazaki, Shuichi Sakai
Publication date: 9 March 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items (33)
Maximum weighted induced subgraphs ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ Minimum-energy wireless real-time multicast by joint network coding and scheduling optimization ⋮ On vertex independence number of uniform hypergraphs ⋮ A genetic algorithm for scheduling open shops with conflict graphs to minimize the makespan ⋮ Greed is good for deterministic scale-free networks ⋮ Flow shop scheduling problem with conflict graphs ⋮ Slack allocation algorithm for parallel machines ⋮ An exact algorithm for MAX-CUT in sparse graphs ⋮ Recoverable Values for Independent Sets ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ The maximum volume hard subset model for Poisson processes: simulation aspects ⋮ Bounding the feedback vertex number of digraphs in terms of vertex degrees ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Data dependent worst case bounds for weighted set packing ⋮ Indirect unstructured hex-dominant mesh generation using tetrahedra recombination ⋮ Facility location with tree topology and radial distance constraints ⋮ Simple and local independent set approximation ⋮ Hardness of and approximate mechanism design for the bike rebalancing problem ⋮ Gene selection via a new hybrid ant colony optimization algorithm for cancer classification in high-dimensional data ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ A PAC Approach to Application-Specific Algorithm Selection ⋮ Unnamed Item ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Independent sets in bounded-degree hypergraphs ⋮ MAX for \(k\)-independence in multigraphs ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs ⋮ Carpal tunnel syndrome automatic classification: electromyography vs. ultrasound imaging ⋮ A branch-and-price approach for the continuous multifacility monotone ordered median problem ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees ⋮ Open shop scheduling problems with conflict graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Small transversals in hypergraphs
- Stable sets and polynomials
- The maximum clique problem
- A probabilistic lower bound on the independence number of graphs
- Lower bounds on the independence number in terms of the degrees
This page was built for publication: A note on greedy algorithms for the maximum weighted independent set problem
