Approximating maximum independent sets by excluding subgraphs
From MaRDI portal
Publication:1196452
DOI10.1007/BF01994876zbMath0761.68044WikidataQ29013889 ScholiaQ29013889MaRDI QIDQ1196452
Magnús M. Halldórsson, Ravi B. Boppana
Publication date: 14 December 1992
Published in: BIT (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (48)
Towards optimal lower bounds for clique and chromatic number. ⋮ On the approximability of clique and related maximization problems ⋮ Topological graph persistence ⋮ Phased local search for the maximum clique problem ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ Improved approximations of independent sets in bounded-degree graphs ⋮ Hard graphs for randomized subgraph exclusion algorithms ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ MNP: A class of NP optimization problems ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Approximating the independence number via the \(\vartheta\)-function ⋮ On chromatic sums and distributed resource allocation ⋮ Time slot scheduling of compatible jobs ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ On the approximability of the maximum common subgraph problem ⋮ On vertex independence number of uniform hypergraphs ⋮ Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE ⋮ The power of amortized recourse for online graph problems ⋮ Maximum Weighted Independent Sets with a Budget ⋮ Cutting planes cannot approximate some integer programs ⋮ Independent sets with domination constraints ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ On-line resource management with applications to routing and scheduling ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ In search of the densest subgraph ⋮ A still better performance guarantee for approximate graph coloring ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ The complexity of detecting fixed-density clusters ⋮ Reoptimization of Weighted Graph and Covering Problems ⋮ Mining relevant information on the Web: a clique-based approach ⋮ On the independent set problem in random graphs ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Approximating the maximum vertex/edge weighted clique using local search ⋮ Multitasking Capacity: Hardness Results and Improved Constructions ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ On a scheduling problem of time deteriorating jobs ⋮ Zero knowledge and the chromatic number ⋮ Detecting a botnet in a network ⋮ Priority algorithms for graph optimization problems ⋮ The variational quantum eigensolver: a review of methods and best practices ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ The inapproximability of non-NP-hard optimization problems. ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Heuristics for semirandom graph problems ⋮ The maximum clique problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- A better performance guarantee for approximate graph coloring
- A note on the independence number of triangle-free graphs
- A note on Ramsey numbers
- On the complexity of approximating the independent set problem
- Approximating maximum independent sets by excluding subgraphs
- Proof verification and the hardness of approximation problems
- Improving the performance guarantee for approximate graph coloring
- Probabilistic checking of proofs
This page was built for publication: Approximating maximum independent sets by excluding subgraphs
