On the public citation graph
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
0 signed · 79 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.1007/11786986_21openalex-snapshot
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
inferredcites →https://doi.org/10.1007/3-540-48686-0_26openalex-snapshot
Approximations of Weighted Independent Set and Hereditary Subset Problems
inferredcites →https://doi.org/10.1007/978-3-642-14165-2_22openalex-snapshot
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1016/j.jcss.2007.06.019openalex-snapshot
Vertex cover might be hard to approximate to within 2−ε
inferredcites →https://doi.org/10.1023/b:joco.0000038911.67280.3fopenalex-snapshot
On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function
inferredcites →https://doi.org/10.1109/ccc.2002.1004334openalex-snapshot
On the power of unique 2-prover 1-round games
inferredcites →https://doi.org/10.1109/focs.2008.44openalex-snapshot
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes
inferredcites →https://doi.org/10.1109/focs.2008.51openalex-snapshot
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
inferredcites →https://doi.org/10.1109/focs.2009.23openalex-snapshot
Optimal Long Code Test with One Free Bit
inferredcites →https://doi.org/10.1137/07068062xopenalex-snapshot
Conditional Hardness for Approximate Coloring
inferredcites →https://doi.org/10.1137/s0097539700381097openalex-snapshot
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
inferredcites →https://doi.org/10.1137/s0097539705447372openalex-snapshot
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
inferredcites →https://doi.org/10.1137/s089548010240415xopenalex-snapshot
Approximating Maximum Clique by Removing Subgraphs
inferredcites →https://doi.org/10.1145/1132516.1132519openalex-snapshot
Gowers uniformity, influence of variables, and PCPs
inferredcites →https://doi.org/10.1145/1132516.1132567openalex-snapshot
Conditional hardness for approximate coloring
inferredcites →https://doi.org/10.1145/1250790.1250818openalex-snapshot
Balanced max 2-sat might not be the hardest
inferredcites →https://doi.org/10.1145/1597036.1597045openalex-snapshot
A better approximation ratio for the vertex cover problem
inferredcites →https://doi.org/10.1145/335305.335329openalex-snapshot
A PCP characterization of NP with optimal amortized query complexity
inferredcites →https://doi.org/10.1145/509907.510017openalex-snapshot
On the power of unique 2-prover 1-round games
inferredcites →https://doi.org/10.4007/annals.2005.162.439openalex-snapshot
On the hardness of approximating vertex cover
inferredcites →https://doi.org/10.4007/annals.2010.171.295openalex-snapshot
Noise stability of functions with low influences: Invariance and optimality
inferredcites →https://doi.org/10.48550/arxiv.0912.1776openalex-snapshot
On the Optimality of a Class of LP-based Algorithms
inferredcites →https://doi.org/10.7155/jgaa.00020openalex-snapshot
Approximations of Weighted Independent Set and Hereditary Subset Problems
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-1-4614-0754-6_10openalex-snapshot
Hardness Complexity of Optimal Substructure Problems on Power-Law Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-01325-7_12openalex-snapshot
Simple and Local Independent Set Approximation
inferred← citeshttps://doi.org/10.1007/978-3-031-27051-2_30openalex-snapshot
On the Parameterized Complexity of Compact Set Packing
inferred← citeshttps://doi.org/10.1007/978-3-031-82670-2_22openalex-snapshot
Forest Covers and Bounded Forest Covers
inferred← citeshttps://doi.org/10.1007/978-3-319-53007-9_23openalex-snapshot
Maximum Weighted Independent Sets with a Budget
inferred← citeshttps://doi.org/10.1007/978-3-319-71150-8_17openalex-snapshot
New Insights for Power Edge Set Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-12683-3_2openalex-snapshot
SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings
inferred← citeshttps://doi.org/10.1007/978-3-642-13036-6_28openalex-snapshot
On k-Column Sparse Packing Programs
inferred← citeshttps://doi.org/10.1007/978-3-642-14162-1_28openalex-snapshot
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests
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-17458-2_17openalex-snapshot
On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_41openalex-snapshot
Recoverable Values for Independent Sets
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_42openalex-snapshot
Vertex Cover in Graphs with Locally Few Colors
inferred← citeshttps://doi.org/10.1007/978-3-642-23151-3_5openalex-snapshot
Mining Biological Networks for Similar Patterns
inferred← citeshttps://doi.org/10.1007/978-3-642-25870-1_10openalex-snapshot
Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses
inferred← citeshttps://doi.org/10.1007/978-3-642-40104-6_8openalex-snapshot
Socially Stable Matchings in the Hospitals/Residents Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-40450-4_26openalex-snapshot
Secluded Connectivity Problems
inferred← citeshttps://doi.org/10.1007/s00145-012-9124-7openalex-snapshot
Logic Minimization Techniques with Applications to Cryptology
inferred← citeshttps://doi.org/10.1007/s00224-015-9638-0openalex-snapshot
Complexity of Approximating CSP with Balance / Hard Constraints
inferred← citeshttps://doi.org/10.1007/s00453-012-9633-7openalex-snapshot
Donation Center Location Problem
inferred← citeshttps://doi.org/10.1007/s00453-016-0222-zopenalex-snapshot
Secluded Connectivity Problems
inferred← citeshttps://doi.org/10.1007/s00453-024-01269-6openalex-snapshot
On the Parameterized Complexity of Compact Set Packing
inferred← citeshttps://doi.org/10.1007/s10107-017-1221-9openalex-snapshot
Affine reductions for LPs and SDPs
inferred← citeshttps://doi.org/10.1007/s10878-026-01466-9openalex-snapshot
Directed star packing: Tractability, inapproximability, and approximation algorithms
inferred← citeshttps://doi.org/10.1007/s40305-018-00237-6openalex-snapshot
Competitive and Collaborative Influence in Social Networks
inferred← citeshttps://doi.org/10.1007/s40305-019-00260-1openalex-snapshot
Approximation Algorithms for Vertex Happiness
inferred← citeshttps://doi.org/10.1016/j.ic.2011.12.008openalex-snapshot
Vertex cover in graphs with locally few colors
inferred← citeshttps://doi.org/10.1016/j.jda.2014.12.010openalex-snapshot
Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs
inferred← citeshttps://doi.org/10.1016/j.jda.2018.11.006openalex-snapshot
Complexity and lowers bounds for Power Edge Set Problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.10.023openalex-snapshot
New techniques for approximating optimal substructure problems in power-law 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.1109/focs.2019.00040openalex-snapshot
Inapproximability of Clustering in Lp Metrics
inferred← citeshttps://doi.org/10.1109/tnet.2012.2186462openalex-snapshot
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests
inferred← citeshttps://doi.org/10.1137/1.9781611973730.1openalex-snapshot
Approximating independent sets in sparse graphs
inferred← citeshttps://doi.org/10.1137/1.9781611976465.26openalex-snapshot
Approximation Algorithms and Hardness for Strong Unique Games
inferred← citeshttps://doi.org/10.1137/1.9781611977073.40openalex-snapshot
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
inferred← citeshttps://doi.org/10.1137/1.9781611977073.63openalex-snapshot
Johnson Coverage Hypothesis: Inapproximability of k -means and k -median in ℓ p -metrics
inferred← citeshttps://doi.org/10.1137/16m1070670openalex-snapshot
Inapproximability of $H$-Transversal/Packing
inferred← citeshttps://doi.org/10.1145/2554797.2554837openalex-snapshot
Complexity of approximating CSP with balance / hard constraints
inferred← citeshttps://doi.org/10.1145/2746539.2746550openalex-snapshot
Inapproximability of Combinatorial Problems via Small LPs and SDPs
inferred← citeshttps://doi.org/10.1145/3087801.3087806openalex-snapshot
Distributed Approximation of Maximum Independent Set and Maximum Matching
inferred← citeshttps://doi.org/10.1184/r1/6606422openalex-snapshot
Inapproximability of $H$-Transversal/Packing
inferred← citeshttps://doi.org/10.1609/aaai.v25i1.7889openalex-snapshot
On Expressing Value Externalities in Position Auctions
inferred← citeshttps://doi.org/10.18653/v1/2022.emnlp-main.242openalex-snapshot
Towards Reinterpreting Neural Topic Models via Composite Activations
inferred← citeshttps://doi.org/10.3233/faia200080openalex-snapshot
Inequity Aversion Pricing in Multi-Unit Markets
inferred← citeshttps://doi.org/10.48550/arxiv.0912.1776openalex-snapshot
On the Optimality of a Class of LP-based Algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1207.1265openalex-snapshot
Locally Stable Marriage with Strict Preferences
inferred← citeshttps://doi.org/10.48550/arxiv.1303.2041openalex-snapshot
Socially stable matchings in the Hospitals / Residents problem
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.55214/25768484.v8i6.4020openalex-snapshot
Fast algorithms for edge coloring in clustered hypergraphs: A study of computational efficiency
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.