Algorithms for the maximum weight connected k-induced subgraph problem

DOI10.1007/978-3-319-12691-3_21MaRDI QIDQ2942405zbMATH OpenOpenAlexFDO

Authors Ernst Althaus, Markus Blumenstock, Alexej Disterhoft, Andreas Hildebrandt, Markus Krupp

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-12691-3_21

zbMATH Keywords

\(k\)-cardinality treebioinformaticsgene regulationheuristicslinear programmingtree decomposition

Mathematics Subject Classification ID

Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• A relax-and-cut framework for large-scale maximum weight connected subgraph problems
• Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
• The Maximum Weight Connected Subgraph Problem
• Approximation hardness of the cross-species conserved active modules detection problem
• Algorithms for the constrained maximum-weight connected graph problem

Cites work

• A constant-factor approximation algorithm for the \(k\)-MST problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 1445374 (Why is no real title available?)
• Improved Steiner tree algorithms for bounded treewidth
• Integer Programming Formulation of Traveling Salesman Problems
• Integer Programming Formulations for the k-Cardinality Tree Problem
• Integrating CSP Decomposition Techniques and BDDs for Compiling Configuration Problems
• New metaheuristic approaches for the edge-weighted k-cardinality tree problem
• Obtaining Optimalk-Cardinality Trees Fast
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• The dense \(k\)-subgraph problem
• The Maximum Weight Connected Subgraph Problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure

Cited in

(17)

• A robust and scalable algorithm for the Steiner problem in graphs
• A relax-and-cut framework for large-scale maximum weight connected subgraph problems
• Solving generalized maximum-weight connected subgraph problem for network enrichment analysis
• The maximum happy induced subgraph problem: bounds and algorithms
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• Reoptimization of maximum weight induced hereditary subgraph problems
• scientific article; zbMATH DE number 1300393 (Why is no real title available?)
• scientific article; zbMATH DE number 1099637 (Why is no real title available?)
• Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
• Approximation hardness of the cross-species conserved active modules detection problem
• Algorithmic aspects of heterogeneous biological networks comparison
• A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality
• The Maximum Weight Connected Subgraph Problem
• Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems
• LATIN 2004: Theoretical Informatics
• Solving the multiobjective quasi-clique problem
• Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems

This page was built for publication: Algorithms for the maximum weight connected \(k\)-induced subgraph problem

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