On the parameterized complexity of the expected coverage problem

DOI10.1007/S00224-022-10073-0MaRDI QIDQ2135628zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Vijayaragunathan Ramamoorthi

Publication date 9 May 2022

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-022-10073-0

zbMATH Keywords

treewidthfacility locationpathwidthW[1-hard]negative demands

Mathematics Subject Classification ID

Operations research and management science (90Bxx) Theory of computing (68Qxx) Graph theory (05Cxx)

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
• Reliability problems in multiple path-shaped facility location on networks

Cites work

• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1405654 (Why is no real title available?)
• 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
• 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
• 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

(4)

• Implicit branching and parameterized partial cover problems
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
• Presolving and cutting planes for the generalized maximal covering location problem
• 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 Q2135628)