On the Parameterized Complexity of the Expected Coverage Problem

DOI10.1007/978-3-030-50026-9_16OpenAlexW3036963223MaRDI QIDQ5042243

Vijayaragunathan Ramamoorthi, Fedor V. Fomin

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-50026-9_16

zbMATH Keywords

treewidthfacility locationapex-minor-free graphW[1-hard]subexponential parameterized algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
• Generalized coverage: new developments in covering location models
• A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges
• Treewidth. Computations and approximations
• The budgeted maximum coverage problem
• Facility location on planar graphs with unreliable links
• Multiple facility location on a network with linear reliability order of edges
• Subexponential algorithms for partial cover problems
• Facility location problems: a parameterized view
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• Graph Theory
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Polynomial-time data reduction for dominating set
• Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links
• Location of facilities on a network subject to a single‐edge failure
• Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
• Kernelization and Sparseness: the case of Dominating Set
• Parameterized complexity: exponential speed-up for planar graph problems
• A single facility location problem on a tree with unreliable edges
• The Parameterized Hardness of the k-Center Problem in Transportation Networks
• Bidimensionality and Geometric Graphs
• Partial vs. Complete Domination: t-Dominating Set
• Parameterized Algorithms

This page was built for publication: On the Parameterized Complexity of the Expected Coverage Problem