Pages that link to "Item:Q1588908"
From MaRDI portal
The following pages link to Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908):
Displaying 50 items.
- The complexity of estimating min-entropy (Q260395) (← links)
- Shrinking maxima, decreasing costs: new online packing and covering problems (Q289907) (← links)
- A lower bound on the independence number of a graph in terms of degrees and local clique sizes (Q298956) (← links)
- On the computational complexity of the virtual network embedding problem (Q325446) (← links)
- Coloring immersion-free graphs (Q326817) (← links)
- Common information and unique disjointness (Q343843) (← links)
- A copositive formulation for the stability number of infinite graphs (Q344928) (← links)
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation (Q358656) (← links)
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations (Q360375) (← links)
- Strong lift-and-project cutting planes for the stable set problem (Q378110) (← links)
- A note on anti-coordination and social interactions (Q386417) (← links)
- Moderately exponential approximation for makespan minimization on related machines (Q392019) (← links)
- New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix (Q396873) (← links)
- Complexity of finding maximum regular induced subgraphs with prescribed degree (Q401302) (← links)
- An exact algorithm for the maximum probabilistic clique problem (Q405671) (← links)
- Staying safe and visible via message sharing in online social networks (Q405681) (← links)
- Partial multicovering and the \(d\)-consecutive ones property (Q408373) (← links)
- Geometric rounding: A dependent randomized rounding scheme (Q411220) (← links)
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane (Q412277) (← links)
- Copositive optimization -- recent developments and applications (Q421783) (← links)
- Approximability of constrained LCS (Q439929) (← links)
- On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs (Q448967) (← links)
- Approximation algorithms for maximum independent set of pseudo-disks (Q452004) (← links)
- Cutting planes cannot approximate some integer programs (Q453048) (← links)
- On the inapproximability of maximum intersection problems (Q456103) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- 2-approximation algorithm for finding a clique with minimum weight of vertices and edges (Q483409) (← links)
- Approximability of the subset sum reconfiguration problem (Q489711) (← links)
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph (Q492279) (← links)
- Hardness of computing clique number and chromatic number for Cayley graphs (Q518185) (← links)
- Finding quasi core with simulated stacked neural networks (Q526647) (← links)
- Complexity issues for the sandwich homogeneous set problem (Q531596) (← links)
- A lower bound on independence in terms of degrees (Q548268) (← links)
- Independence in connected graphs (Q617904) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- On the complexity of reconfiguration problems (Q631762) (← links)
- Constant-degree graph expansions that preserve treewidth (Q633842) (← links)
- Graph problems arising from parameter identification of discrete dynamical systems (Q634788) (← links)
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover (Q646517) (← links)
- The complexity of König subgraph problems and above-guarantee vertex cover (Q652520) (← links)
- Distributed discovery of large near-cliques (Q661050) (← links)
- Computing the partition function for graph homomorphisms (Q681595) (← links)
- Maximum regular induced subgraphs in \(2P_3\)-free graphs (Q690473) (← links)
- Minimum entropy combinatorial optimization problems (Q693045) (← links)
- On the complexity of fixed parameter clique and dominating set (Q703534) (← links)
- Project scheduling with irregular costs: complexity, approximability, and algorithms (Q707495) (← links)
- Interpolating between bounds on the independence number (Q708394) (← links)
- Hyperbolic set covering problems with competing ground-set elements (Q715069) (← links)
- On linear and semidefinite programming relaxations for hypergraph matching (Q715088) (← links)
- Lower bounds for treewidth of product graphs (Q741743) (← links)
