Polynomial-Time Data Reduction for the Subset Interconnection Design Problem

DOI10.1137/140955057zbMath1326.05147OpenAlexW2013504716MaRDI QIDQ3453561

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

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

NP-hard problemcombinatorial algorithmsfixed-parameter tractabilitykernelizationpreprocessinghypergraph support

Mathematics Subject Classification ID

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

Related Items (8)

Twins in Subdivision Drawings of Hypergraphs ⋮ A Computational Study of Reduction Techniques for the Minimum Connectivity Inference Problem ⋮ Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem ⋮ The minimum feasible tileset problem ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Overlaying a hypergraph with a graph with bounded maximum degree ⋮ An improved flow-based formulation and reduction principles for the minimum connectivity inference problem ⋮ Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

This page was built for publication: Polynomial-Time Data Reduction for the Subset Interconnection Design Problem