Pages that link to "Item:Q1184733"
From MaRDI portal
The following pages link to On the complexity of approximating the independent set problem (Q1184733):
Displaying 50 items.
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP (Q293222) (← links)
- A natural family of optimization problems with arbitrarily small approximation thresholds (Q293457) (← links)
- Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems (Q293458) (← links)
- A note on anti-coordination and social interactions (Q386417) (← links)
- Kernel bounds for path and cycle problems (Q392032) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs (Q496657) (← links)
- Approximate solution of NP optimization problems (Q672315) (← links)
- Approximation algorithm for DNF under distributions with limited independence (Q675867) (← links)
- Complexities of efficient solutions of rectilinear polygon cover problems (Q676264) (← links)
- On approximating the longest path in a graph (Q679451) (← links)
- Approximating the minimum maximal independence number (Q685520) (← links)
- On approximating the minimum independent dominating set (Q750159) (← links)
- On approximation problems related to the independent set and vertex cover problems (Q760210) (← links)
- On approximating four covering and packing problems (Q1021577) (← links)
- On the hardness of approximating max-satisfy (Q1045886) (← links)
- Optimization, approximation, and complexity classes (Q1186548) (← links)
- Approximating maximum independent sets by excluding subgraphs (Q1196452) (← links)
- Zero knowledge and the chromatic number (Q1276168) (← links)
- On approximation properties of the independent set problem for low degree graphs (Q1281930) (← links)
- A note on the approximation of a minimum-weight maximal independent set (Q1303785) (← links)
- The complexity and approximability of finding maximum feasible subsystems of linear relations (Q1367542) (← links)
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function (Q1375058) (← links)
- Approximating the independence number via the \(\vartheta\)-function (Q1380939) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- Ramsey theory and integrality gap for the independent set problem (Q1667206) (← links)
- Derandomized graph products (Q1842777) (← links)
- Independence number and the complexity of families of sets (Q1918552) (← links)
- The complexity of irredundant sets parameterized by size (Q1971218) (← links)
- Tilt assembly: algorithms for micro-factories that build objects with uniform external forces (Q1986953) (← links)
- Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas (Q2075363) (← links)
- On the analysis of optimization problems in arc-dependent networks (Q2172089) (← links)
- Faster exponential-time algorithms for approximately counting independent sets (Q2235762) (← links)
- On the complexity of the independent set problem in triangle graphs (Q2275391) (← links)
- On constructing an optimal consensus clustering from multiple clusterings (Q2380012) (← links)
- On approximating the \(d\)-girth of a graph (Q2444552) (← links)
- The resolution complexity of independent sets and vertex covers in random graphs (Q2474203) (← links)
- Inapproximability results for the lateral gene transfer problem (Q2479568) (← links)
- Resource bounds and subproblem independence (Q2581008) (← links)
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis (Q2633244) (← links)
- Analyzing read-once cutting plane proofs in Horn systems (Q2673307) (← links)
- The biclique \(k\)-clustering problem in bipartite graphs and its application in bioinformatics (Q2883562) (← links)
- Finding independent sets in unions of perfect graphs (Q2908854) (← links)
- A fine-grained analysis of a simple independent set algorithm (Q2920136) (← links)
- Recoverable Values for Independent Sets (Q3012827) (← links)
- Exponential Time Complexity of Weighted Counting of Independent Sets (Q3058702) (← links)
- Expander graphs and their applications (Q3514498) (← links)
- Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms (Q4608072) (← links)
- The approximation of maximum subgraph problems (Q4630247) (← links)
- Polynomially bounded minimization problems which are hard to approximate (Q4630248) (← links)
