On the public citation graph
Approximations of independent sets in graphs
0 signed · 107 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/(sici)1520-6750(199608)43:5<737::aid-nav9>3.0.co;2-6openalex-snapshot
On locally optimal independent sets and vertex covers
inferredcites →https://doi.org/10.1007/3-540-58218-5_18openalex-snapshot
Improved approximations of independent sets in bounded-degree graphs
inferredcites →https://doi.org/10.1007/3-540-60220-8_84openalex-snapshot
On approximation properties of the Independent set problem for degree 3 graphs
inferredcites →https://doi.org/10.1007/3-540-60220-8_89openalex-snapshot
Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)
inferredcites →https://doi.org/10.1007/978-0-8176-4842-8_3openalex-snapshot
A Combinatorial Problem in Geometry
inferredcites →https://doi.org/10.1007/bf01196133openalex-snapshot
Randomized graph products, chromatic numbers, and the Lov�sz ?-function
inferredcites →https://doi.org/10.1007/bf01580444openalex-snapshot
Vertex packings: Structural properties and algorithms
inferredcites →https://doi.org/10.1007/bf01581168openalex-snapshot
Approximating the independence number via theϑ-function
inferredcites →https://doi.org/10.1007/bf01994876openalex-snapshot
Approximating maximum independent sets by excluding subgraphs
inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1007/bf02523693openalex-snapshot
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
inferredcites →https://doi.org/10.1007/bf02579196openalex-snapshot
The monotone circuit complexity of boolean functions
inferredcites →https://doi.org/10.1007/bf02579451openalex-snapshot
On Turán’s theorem for sparse graphs
inferredcites →https://doi.org/10.1007/bfb0055051openalex-snapshot
Independent sets with domination constraints
inferredcites →https://doi.org/10.1016/0020-0190(93)90246-6openalex-snapshot
A still better performance guarantee for approximate graph coloring
inferredcites →https://doi.org/10.1016/0095-8956(75)90089-1openalex-snapshot
Three short proofs in graph theory
inferredcites →https://doi.org/10.1016/0166-218x(83)90080-xopenalex-snapshot
Efficient bounds for the stable set, vertex cover and set packing problems
inferredcites →https://doi.org/10.1016/0166-218x(84)90086-6openalex-snapshot
On approximation problems related to the independent set and vertex cover problems
inferredcites →https://doi.org/10.1016/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
inferredcites →https://doi.org/10.1016/s0166-218x(96)00063-7openalex-snapshot
Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
inferredcites →https://doi.org/10.1016/s0893-9659(97)00044-xopenalex-snapshot
Improved approximations for maximum independent set via approximation chains
inferredcites →https://doi.org/10.1023/a:1009755815678openalex-snapshot
Local Optimality and Its Application on Independent Sets for k-claw Free Graphs
inferredcites →https://doi.org/10.1109/sfcs.1977.6openalex-snapshot
Applications of a planar separator theorem
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1994.365710openalex-snapshot
Approximate graph coloring by semidefinite programming
inferredcites →https://doi.org/10.1109/sfcs.1994.365712openalex-snapshot
On syntactic versus computational views of approximability
inferredcites →https://doi.org/10.1109/sfcs.1995.492473openalex-snapshot
Derandomizing semidefinite programming based approximation algorithms
inferredcites →https://doi.org/10.1109/sfcs.1996.548522openalex-snapshot
Clique is hard to approximate within n/sup 1-ε/
inferredcites →https://doi.org/10.1109/tit.1979.1055985openalex-snapshot
On the Shannon capacity of a graph
inferredcites →https://doi.org/10.1137/0402008openalex-snapshot
On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
inferredcites →https://doi.org/10.1145/174644.174650openalex-snapshot
Approximation algorithms for NP-complete problems on planar graphs
inferredcites →https://doi.org/10.1145/2157.2158openalex-snapshot
Improving the performance guarantee for approximate graph coloring
inferredcites →https://doi.org/10.1145/274787.274791openalex-snapshot
Approximate graph coloring by semidefinite programming
inferredcites →https://doi.org/10.1287/moor.23.3.640openalex-snapshot
On Local Search for Weighted k-Set Packing
inferredcites →https://doi.org/10.4064/cm-16-1-253-256openalex-snapshot
Some remarks on chromatic graphs
inferredcites →https://doi.org/10.5555/313651.313687openalex-snapshot
Approximating discrete collections via local improvements
inferredcites →https://doi.org/10.5555/314464.314570openalex-snapshot
Approximating maximum independent set in bounded degree graphs
inferredcites →https://doi.org/10.5555/640160.640166openalex-snapshot
Improved approximations of independent sets in bounded-degree graphs via subgraph removal
inferredcites →https://doi.org/10.7155/jgaa.00003openalex-snapshot
Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11549345_53openalex-snapshot
Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing
inferred← citeshttps://doi.org/10.1007/11604686_30openalex-snapshot
Approximation Algorithms for the Weighted Independent Set Problem
inferred← citeshttps://doi.org/10.1007/11970125_21openalex-snapshot
An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_48openalex-snapshot
The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set
inferred← citeshttps://doi.org/10.1007/978-0-387-68832-9_12openalex-snapshot
Decentralized Spectrum Management Through User Coordination
inferred← citeshttps://doi.org/10.1007/978-3-031-04520-2_8openalex-snapshot
Fast Heuristics and Approximation Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-319-94776-1_26openalex-snapshot
The Path Set Packing Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-45198-3_8openalex-snapshot
On the Complexity of Approximating k-Dimensional Matching
inferred← citeshttps://doi.org/10.1007/978-3-540-73951-7_24openalex-snapshot
Independent Sets in Bounded-Degree Hypergraphs
inferred← citeshttps://doi.org/10.1007/978-3-540-74823-6_6openalex-snapshot
Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum-Weight Independent Set in Local Conflict Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-93980-1_13openalex-snapshot
On Lagrangian Relaxation and Subset Selection Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_3openalex-snapshot
SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_14openalex-snapshot
On Constant Time Approximation of Parameters of Bounded Degree Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-18381-2_12openalex-snapshot
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
inferred← citeshttps://doi.org/10.1007/978-3-8351-9067-2_3openalex-snapshot
Approximation mit relativer Gütegarantie
inferred← citeshttps://doi.org/10.1007/s00037-006-0205-6openalex-snapshot
On the complexity of approximating k-set packing
inferred← citeshttps://doi.org/10.1007/s00454-012-9417-5openalex-snapshot
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
inferred← citeshttps://doi.org/10.1007/s10458-010-9123-8openalex-snapshot
Coalition formation for task allocation: theory and algorithms
inferred← citeshttps://doi.org/10.1007/s10878-010-9320-zopenalex-snapshot
Geometric rounding: a dependent randomized rounding scheme
inferred← citeshttps://doi.org/10.1007/s10951-019-00633-7openalex-snapshot
Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments
inferred← citeshttps://doi.org/10.1007/s11036-008-0086-9openalex-snapshot
Understanding the Power of Distributed Coordination for Dynamic Spectrum Management
inferred← citeshttps://doi.org/10.1007/s11276-009-0219-5openalex-snapshot
Computational aspects of optimal schedules with power control and multiple bitrates selection in multihop wireless networks
inferred← citeshttps://doi.org/10.1016/j.dam.2004.11.007openalex-snapshot
Conversion of coloring algorithms into maximum weight independent set algorithms
inferred← citeshttps://doi.org/10.1016/j.dam.2008.08.027openalex-snapshot
Approximation algorithms for the weighted independent set problem in sparse graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2008.11.013openalex-snapshot
Independent sets in bounded-degree hypergraphs
inferred← citeshttps://doi.org/10.1016/j.dam.2011.04.023openalex-snapshot
The complexity of dissociation set problems in graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2020.10.001openalex-snapshot
On Lagrangian relaxation for constrained maximization and reoptimization problems
inferred← citeshttps://doi.org/10.1016/j.dam.2024.10.023openalex-snapshot
Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2025.02.040openalex-snapshot
A heuristic algorithm for rainbow matchings and its application in rainbow Ramsey number for matchings
inferred← citeshttps://doi.org/10.1016/j.disc.2011.04.001openalex-snapshot
On the complexity of the independent set problem in triangle graphs
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.04.001openalex-snapshot
On packing shortest cycles in graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.11.025openalex-snapshot
SDP-based algorithms for maximum independent set problems on hypergraphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.12.013openalex-snapshot
Complexity results for rainbow matchings
inferred← citeshttps://doi.org/10.1016/s0004-3702(01)00159-xopenalex-snapshot
Algorithm for optimal winner determination in combinatorial auctions
inferred← citeshttps://doi.org/10.1016/s0004-3702(99)00036-3openalex-snapshot
Coalition structure generation with worst case guarantees
inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00110-7openalex-snapshot
On the approximability of clique and related maximization problems
inferred← citeshttps://doi.org/10.1016/s0167-9236(99)00066-4openalex-snapshot
Approaches to winner determination in combinatorial auctions
inferred← citeshttps://doi.org/10.1016/s0927-0507(05)12008-8openalex-snapshot
Semidefinite Programming and Integer Programming
inferred← citeshttps://doi.org/10.1023/a:1011672624624openalex-snapshot
The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set
inferred← citeshttps://doi.org/10.1080/00207540600693713openalex-snapshot
Mining relevant information on the Web: a clique-based approach
inferred← citeshttps://doi.org/10.1080/17445760.2026.2684509openalex-snapshot
Scalable maximum independent set computation for conflict graphs using kernelization and greedy inference
inferred← citeshttps://doi.org/10.1109/ccnc.2006.1593099openalex-snapshot
Route and spectrum selection in dynamic spectrum networks
inferred← citeshttps://doi.org/10.1109/focs.2011.36openalex-snapshot
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
inferred← citeshttps://doi.org/10.1109/infcom.2007.243openalex-snapshot
Toward Tractable Computation of the Capacity of Multi-Hop Wireless Networks
inferred← citeshttps://doi.org/10.1109/jiot.2026.3696701openalex-snapshot
Quantum-Classical Dual LSTM Optimization for Internet of Intelligent Vehicles
inferred← citeshttps://doi.org/10.1109/sahcn.2005.1557100openalex-snapshot
Distributed spectrum allocation via local bargaining
inferred← citeshttps://doi.org/10.1109/tnet.2011.2111462openalex-snapshot
Practical Computation of Optimal Schedules in Multihop Wireless Networks
inferred← citeshttps://doi.org/10.1111/1467-8640.t01-1-00209openalex-snapshot
eMediator: A Next Generation Electronic Commerce Server
inferred← citeshttps://doi.org/10.1137/1.9781611973730.1openalex-snapshot
Approximating independent sets in sparse graphs
inferred← citeshttps://doi.org/10.1145/1542362.1542420openalex-snapshot
Approximation algorithms for maximum independent set of pseudo-disks
inferred← citeshttps://doi.org/10.1145/2488608.2488665openalex-snapshot
Approximation resistance from pairwise independent subgroups
inferred← citeshttps://doi.org/10.1145/3087801.3087806openalex-snapshot
Distributed Approximation of Maximum Independent Set and Maximum Matching
inferred← citeshttps://doi.org/10.1145/335305.335322openalex-snapshot
The value of strong inapproximability results for clique
inferred← citeshttps://doi.org/10.1145/380752.380839openalex-snapshot
Non-approximability results for optimization problems on bounded degree instances
inferred← citeshttps://doi.org/10.14232/actacyb.21.3.2014.12openalex-snapshot
Applications of the Inverse Theta Number in Stable Set Problems
inferred← citeshttps://doi.org/10.3182/20090603-3-ru-2001.0071openalex-snapshot
On the Complexity of Dissociation Set Problems in Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1103.1431openalex-snapshot
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
inferred← citeshttps://doi.org/10.48550/arxiv.1507.07459openalex-snapshot
On local search and LP and SDP relaxations for k-Set Packing
inferred← citeshttps://doi.org/10.48550/arxiv.1512.06736openalex-snapshot
On Lagrangian Relaxation and Reoptimization Problems
inferred← citeshttps://doi.org/10.48550/arxiv.2008.01961openalex-snapshot
An Algorithm Framework for the Exact Solution and Improved Approximation of the Maximum Weighted Independent Set Problem
inferred← citeshttps://doi.org/10.5555/338219.338269openalex-snapshot
Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs
inferred← citeshttps://doi.org/10.7551/mitpress/9780262033428.003.0013openalex-snapshot
The Winner Determination Problem
inferred← citeshttps://doi.org/10.7936/k74j0cb1openalex-snapshot
An Algorithm for Optimal Winner Determination in Combinatorial Auctions
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.