Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

DOI10.1016/j.disopt.2021.100623zbMath1506.90257OpenAlexW3131105786MaRDI QIDQ2042074

John Martinovic, Andreas Fischer, Muhammad Abid Dar, Guntram Scheithauer

Publication date: 27 July 2021

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2021.100623

zbMATH Keywords

polytopesmodel reductionminimum spanning treeMILPminimum connectivity inference

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Clustering with prim's sequential representation of minimum spanning tree
• On the approximability and hardness of minimum topic connected overlay and its special instances
• Resonance, stability and chaotic vibration of a quarter-car vehicle model with time-delay feedback
• Solving the minimum label spanning tree problem by mathematical programming techniques
• New models of the generalized minimum spanning tree problem
• An optimization problem on graphs
• Using separation algorithms to generate mixed integer model reformulations
• On complexity of subset interconnection designs
• A graph-theoretical clustering method based on two rounds of minimum spanning trees
• Connectivity Inference in Mass Spectrometry Based Structure Determination
• Integer Programming Formulations for Minimum Spanning Forests and Connected Components in Sparse Graphs
• Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
• Matroids and Subset Interconnection Design
• Two algorithms for the subset interconnection design problem
• Inferring Social Networks from Outbreaks
• A Computational Study of Reduction Techniques for the Minimum Connectivity Inference Problem
• An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
• Constructing scalable overlays for pub-sub with many topics
• Algorithms and Implementation for Interconnection Graph Problem
• Extended formulations in combinatorial optimization

This page was built for publication: Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles