On the complexity of the Maximum Subgraph Problem
From MaRDI portal
Publication:5402566
DOI10.1145/800133.804356zbMath1282.68124OpenAlexW2031967239MaRDI QIDQ5402566
Publication date: 14 March 2014
Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/800133.804356
Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)
Related Items
Fixed-parameter tractability of graph modification problems for hereditary properties ⋮ Mathematical programming approaches for dual multicast routing problem with multilayer risk cost ⋮ The node-deletion problem for hereditary properties is NP-complete ⋮ Combinatorial problems over power sets ⋮ Local approximations for maximum partial subgraph problem. ⋮ The complexity of uniform Nash equilibria and related regular subgraph problems ⋮ Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties ⋮ Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms ⋮ A good submatrix is hard to find ⋮ Edge-contraction problems
