Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
type: Item
instance of: scholarly article
title: Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
zbMATH Open document ID: 1410.68161
author: Nathann Cohen
author: Frédéric Havet
author: Dorian Mazauric
author: Ignasi Sau
author: Rémi Watrigant
published in: Journal of Discrete Algorithms
publication date: 2019-01-18T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7003354
zbMATH Keywords: hypergraph
zbMATH Keywords: minimum \(\mathcal{F}\)-overlay problem
zbMATH Keywords: NP-completeness
zbMATH Keywords: fixed-parameter tractability
MaRDI profile type: Publication
full work available at URL: j.jda.2018.11.010
OpenAlex ID: W2601571902
cites work: Inferring Social Networks from Outbreaks
cites work: Blocks of Hypergraphs
cites work: Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
cites work: Constructing scalable overlays for pub-sub with many topics
cites work: Fundamentals of parameterized complexity
cites work: On complexity of subset interconnection designs
cites work: Matroids and Subset Interconnection Design
cites work: Algorithms and Implementation for Interconnection Graph Problem
cites work: On the approximability and hardness of minimum topic connected overlay and its special instances
cites work: Hypergraph planarity and the complexity of drawing venn diagrams
cites work: Minimum Tree Supports for Hypergraphs and Low-Concurrency Euler Diagrams
cites work: The clustering matroid and the optimal clustering tree
DOI: 10.1016/J.JDA.2018.11.010
description: scientific article; zbMATH DE number 7003354