The approximation of maximum subgraph problems
From MaRDI portal
Recommendations
- On the complexity of the maximum subgraph problem
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- An approximation algorithm for the maximum spectral subgraph problem
- On the approximability of the maximum common subgraph problem
- Approximating maximum diameter-bounded subgraphs
- Approximating Maximum Subgraphs without Short Cycles
- Approximating maximum subgraphs without short cycles
- Approximate Max k-Cut with subgraph guarantee
Cites work
- Applications of a Planar Separator Theorem
- Edge-Deletion Problems
- Efficient probabilistically checkable proofs and applications to approximations
- Fully parallelized multi-prover protocols for NEXP-time
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 3355077 (Why is no real title available?)
- scientific article; zbMATH DE number 3400923 (Why is no real title available?)
- Node-Deletion NP-Complete Problems
- On Approximate Solutions for Combinatorial Optimization Problems
- On the approximability of the maximum common subgraph problem
- On the complexity of approximating the independent set problem
- On the hardness of approximating minimization problems
- Optimization, approximation, and complexity classes
- Planar graphs: Theory and algorithms
- Simple Constructions of Almost k-wise Independent Random Variables
- Some simplified NP-complete graph problems
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- The node-deletion problem for hereditary properties is NP-complete
Cited in
(66)- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- Approximating the maximum clique minor and some subgraph homeomorphism problems
- A new approach for approximating node deletion problems
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- A unified approximation algorithm for node-deletion problems
- Finding optimal subgraphs by local search
- Domination analysis of combinatorial optimization problems.
- Local approximations for maximum partial subgraph problem.
- Approximating minimum feedback vertex sets in hypergraphs
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Online algorithms for the maximum \(k\)-colorable subgraph problem
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Fast constructive and improvement heuristics for edge clique covering
- The maximum happy induced subgraph problem: bounds and algorithms
- An approximation algorithm for the maximum spectral subgraph problem
- Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms
- Strong hardness of approximation for tree transversals
- On the d-claw vertex deletion problem
- Hitting forbidden minors: approximation and kernelization
- Improved bounds on induced acyclic subgraphs in random digraphs
- Approximating maximum diameter-bounded subgraphs
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
- scientific article; zbMATH DE number 3910425 (Why is no real title available?)
- Reoptimization of maximum weight induced hereditary subgraph problems
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Tight Bounds for the Maximum Acyclic Subgraph Problem
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- A survey on the structure of approximation classes
- scientific article; zbMATH DE number 1833409 (Why is no real title available?)
- Bandwidth allocation in cellular networks with multiple interferences
- On the max min vertex cover problem
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Proximity Search for Maximal Subgraph Enumeration
- scientific article; zbMATH DE number 7525474 (Why is no real title available?)
- The Maximum k-Colorable Subgraph Problem and Related Problems
- A tight extremal bound on the Lovász cactus number in planar graphs
- On the approximability of the maximum common subgraph problem
- Inductive graph invariants and approximation algorithms
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- A linear-time algorithm for finding induced planar subgraphs
- Inapproximability of \(H\)-transversal/packing
- On the complexity of the maximum subgraph problem
- Towards Finding Maximal Subrelations with Desired Properties
- Algorithms – ESA 2005
- The maximum feasible subset problem (maxFS) and applications
- A polyhedral study of the maximum edge subgraph problem
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- A generalization of maximal independent sets
- Complexity classification of some edge modification problems
- Structure in approximation classes
- Scheduling with machine conflicts
- Drawing Order Diagrams Through Two-Dimension Extension
- On the \(d\)-claw vertex deletion problem
- An improved algorithm for finding maximum outerplanar subgraphs
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- String editing under pattern constraints
- The maximum k-colorable subgraph problem and orbitopes
- A constant-factor approximation for weighted bond cover
- On minimum t-claw deletion in split graphs
- The algorithmic power of the Greene-Kleitman theorem
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
This page was built for publication: The approximation of maximum subgraph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4630247)
