The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
From MaRDI portal
Publication:3854626
DOI10.1145/322154.322157zbMath0421.68047OpenAlexW2051937719MaRDI QIDQ3854626
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322154.322157
approximationNP-hardinduced subgraphNP-completepolynomial hierarchyhereditary propertynode-deletion problemconnected maximum subgraph problem
Related Items
BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES, On the connectivity preserving minimum cut problem, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, On the approximability of the maximum common subgraph problem, Finding connected secluded subgraphs, Combinatorial problems over power sets, Edge deletion to tree-like graph classes, How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks, Submatrices of non-tree-realizable distance matrices, Contracting graphs to paths and trees, The approximation of maximum subgraph problems, \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems, CNF and DNF succinct graph encodings, Polynomial kernels for deletion to classes of acyclic digraphs, On the complexity of some subgraph problems, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Unnamed Item, Parameterized algorithms for finding highly connected solution, Unnamed Item, Fast and compact planar embeddings, On the NP-hardness of edge-deletion and -contraction problems, Trees related to realizations of distance matrices, The largest tree in a random graph, Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds, Edge-contraction problems, Navigating planar topologies in near-optimal space and time, Parameterized algorithms for finding highly connected solution
