Polynomial-time data reduction for the subset interconnection design problem

DOI10.1137/140955057MaRDI QIDQ3453561zbMATH OpenOpenAlexFDO

Authors Jiehua Chen, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Ondřej Suchý, Mathias Weller

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-01349211/file/Subset_Interconnection_Design-SIDMA.pdf

zbMATH Keywords

fixed-parameter tractabilitykernelizationcombinatorial algorithmspreprocessingNP-hard problemhypergraph support

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Hypergraphs (05C65)

Recommendations

• Effective and efficient data reduction for the subset interconnection design problem
• On complexity of subset interconnection designs
• Polynomial-time data reduction for dominating set
• Two algorithms for the subset interconnection design problem
• A special case for subset interconnection designs

Cited in

(12)

• An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
• Solving problems on generalized convex graphs via mim-width
• Twins in Subdivision Drawings of Hypergraphs
• The role of twins in computing planar supports of hypergraphs
• A computational study of reduction techniques for the minimum connectivity inference problem
• On the complexity of community-aware network sparsification
• Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
• Placing green bridges optimally, with a multivariate analysis
• Overlaying a hypergraph with a graph with bounded maximum degree
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
• Effective and efficient data reduction for the subset interconnection design problem

This page was built for publication: Polynomial-time data reduction for the subset interconnection design problem

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