The approximation of maximum subgraph problems

DOI10.1007/3-540-56939-1_60zbMath1422.68087OpenAlexW1563577400MaRDI QIDQ4630247

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_60

zbMATH Keywords

graph property planar graph hereditary property acyclic digraph subgraph problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Online algorithms for the maximum $k$-colorable subgraph problem, Optimizing adiabatic quantum program compilation using a graph-theoretic framework, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, A primal-dual approach to approximation of node-deletion problems for matroidal properties, The Maximum k-Colorable Subgraph Problem and Related Problems, Reoptimization of maximum weight induced hereditary subgraph problems, Finding optimal subgraphs by local search, Inapproximability of $H$-Transversal/Packing, Complexity of finding maximum regular induced subgraphs with prescribed degree, Inductive graph invariants and approximation algorithms, Structure in approximation classes, Strong hardness of approximation for tree transversals, Scheduling with machine conflicts, Domination analysis of combinatorial optimization problems., Drawing Order Diagrams Through Two-Dimension Extension, An improved algorithm for finding maximum outerplanar subgraphs, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Unnamed Item, On the $d$-claw vertex deletion problem, PTAS for $\mathcal{H}$-free node deletion problems in disk graphs, Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization, A survey on the structure of approximation classes, Local approximations for maximum partial subgraph problem., The maximum $k$-colorable subgraph problem and orbitopes, Bandwidth allocation in cellular networks with multiple interferences, On the max min vertex cover problem, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, 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, Unnamed Item, Fast constructive and improvement heuristics for edge clique covering, Complexity classification of some edge modification problems, Unnamed Item, Efficient algorithms for measuring the funnel-likeness of DAGs, Hitting Forbidden Minors: Approximation and Kernelization, Advice complexity of priority algorithms, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, On the $d$-claw vertex deletion problem, An improved algorithm for the longest induced path problem on $k$-chordal graphs, Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs, Approximating the maximum clique minor and some subgraph homeomorphism problems, A unified approximation algorithm for node-deletion problems, A new approach for approximating node deletion problems, Approximating minimum feedback vertex sets in hypergraphs, Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem, A Linear-Time Algorithm for Finding Induced Planar Subgraphs

Cites Work