Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem

DOI10.1007/978-3-319-12691-3_21zbMath1431.90159OpenAlexW2288870393MaRDI QIDQ2942405

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

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

linear programmingheuristicstree decompositionbioinformaticsgene regulation\(k\)-cardinality tree

Mathematics Subject Classification ID

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

Related Items (2)

A robust and scalable algorithm for the Steiner problem in graphs ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem

Cites Work

• Unnamed Item
• Unnamed Item
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• A constant-factor approximation algorithm for the \(k\)-MST problem
• New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
• Improved Steiner tree algorithms for bounded treewidth
• Detecting high log-densities
• Integer Programming Formulation of Traveling Salesman Problems
• Integer Programming Formulations for the k-Cardinality Tree Problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Obtaining Optimalk-Cardinality Trees Fast
• The Maximum Weight Connected Subgraph Problem
• Integrating CSP Decomposition Techniques and BDDs for Compiling Configuration Problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem

This page was built for publication: Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem