On the parameterized complexity of the expected coverage problem

DOI10.1007/s00224-022-10073-0OpenAlexW4221028137MaRDI QIDQ2135628

Fedor V. Fomin, Vijayaragunathan Ramamoorthi

Publication date: 9 May 2022

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

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

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

Cites Work

• 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
• 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