On the complexity of the maximum subgraph problem

DOI10.1145/800133.804356MaRDI QIDQ5402566zbMATH OpenOpenAlexFDO

Authors John M. Lewis

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

Mathematics Subject Classification ID

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)

Recommendations

• The complexity of regular subgraph recognition
• The approximation of maximum subgraph problems
• scientific article; zbMATH DE number 3910446
• On the complexity of some subgraph problems
• scientific article; zbMATH DE number 30298

Cited in

(32)

• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Reasoning on property graphs with graph generating dependencies
• Edge-contraction problems
• The complexity of the Kth largest subset problem and related problems
• On the complexity of some subgraph problems
• Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms
• The complexity of finding supergraphs
• Algorithms and Computation
• On the complexity of the k-chain subgraph cover problem
• The node-deletion problem for hereditary properties is NP-complete
• scientific article; zbMATH DE number 4047154 (Why is no real title available?)
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Local approximations for maximum partial subgraph problem.
• The complexity of uniform Nash equilibria and related regular subgraph problems
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• The maximum happy induced subgraph problem: bounds and algorithms
• An approximation algorithm for the maximum spectral subgraph problem
• Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
• A good submatrix is hard to find
• scientific article; zbMATH DE number 1833409 (Why is no real title available?)
• The approximation of maximum subgraph problems
• A polyhedral study of the maximum edge subgraph problem
• scientific article; zbMATH DE number 2170471 (Why is no real title available?)
• Mathematical programming approaches for dual multicast routing problem with multilayer risk cost
• scientific article; zbMATH DE number 1099637 (Why is no real title available?)
• Addendum to: The complexity of regular subgraph recognition
• Proximity Search for Maximal Subgraph Enumeration
• Combinatorial problems over power sets
• The Complexity of Mining Maximal Frequent Subgraphs
• On the hardness of computing maximum self-reduction sequences
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)

This page was built for publication: On the complexity of the maximum subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402566)