On the Parameterized Complexity of the Expected Coverage Problem

DOI10.1007/978-3-030-50026-9_16MaRDI QIDQ5042243zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Vijayaragunathan Ramamoorthi

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

apex-minor-free graphfacility locationsubexponential parameterized algorithmtreewidthW[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the parameterized complexity of the expected coverage problem
• Facility location on planar graphs with unreliable links
• Multiple facility location on a network with linear reliability order of edges
• The approximability of multiple facility location on directed networks with random arc failures
• Unreliable point facility location problems on networks

Cites work

• A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
• A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges
• A single facility location problem on a tree with unreliable edges
• Approximation algorithms for NP-hard problems.
• Bidimensionality and kernels
• Facility location on planar graphs with unreliable links
• Facility location problems: a parameterized view
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• Fundamentals of parameterized complexity
• Generalized coverage: new developments in covering location models
• Graph theory
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1405654 (Why is no real title available?)
• Kernelization and Sparseness: the case of Dominating Set
• Kernels for (connected) dominating set on graphs with excluded topological minors
• Location of facilities on a network subject to a single‐edge failure
• Multiple facility location on a network with linear reliability order of edges
• Parameterized algorithms
• Parameterized complexity: exponential speed-up for planar graph problems
• Partial vs. Complete Domination: t-Dominating Set
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• Subexponential algorithms for partial cover problems
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The budgeted maximum coverage problem
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links
• Treewidth. Computations and approximations

Cited in

(3)

• On the parameterized complexity of the expected coverage problem
• On the parameterized complexity of the Maximum Exposure Problem
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles

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

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