On the Parameterized Complexity of the Expected Coverage Problem

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

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (2)

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

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)