Approximation algorithms for the test cover problem
From MaRDI portal
Publication:1424310
DOI10.1007/s10107-003-0414-6zbMath1160.90646OpenAlexW2168924128MaRDI QIDQ1424310
Cor A. J. Hurkens, Jan Karel Lenstra, K. M. J. De Bontridder, Magnús M. Halldórsson, Bjarni V. Halldórsson, R. Ravi, Leen Stougie
Publication date: 11 March 2004
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/18037
Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Sensor placement for fault location identification in water networks: a minimum test cover approach, An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs, A parameterized perspective on packing paths of length two, Deterministic versus randomized adaptive test cover, Integrated model for software component selection with simultaneous consideration of implementation and verification, Mathematical programming in computational biology: an annotated bibliography, The \textsc{red-blue separation} problem on graphs, Local improvement algorithms for a path packing problem: a performance analysis based on linear programming, The stochastic test collection problem: models, exact and heuristic solution approaches, Randomized Adaptive Test Cover, Matching and weighted \(P_2\)-packing: algorithms and kernels, Identifying path covers in graphs, Combinatorial search in two and more rounds, Complexity and approximation for discriminating and identifying code problems in geometric setups, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, The \textsc{Red-Blue Separation} problem on graphs, Approximating the directed path partition problem, On the size of identifying codes in triangle-free graphs, Separating codes and traffic monitoring, Fixed-parameter tractable algorithms for tracking shortest paths, Packing paths: recycling saves time, Combinatorics for smaller kernels: the differential of a graph, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, The generalized test collection problem, Discriminating Codes in Geometric Setups, Set graphs. II. Complexity of set graph recognition and similar problems, Star Partitions of Perfect Graphs, Tight approximability results for test set problems in bioinformatics, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Non-unique probe selection and group testing, A local search algorithm for binary maximum 2-path partitioning, Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs, Vertex and edge covers with clustering properties: Complexity and algorithms, Separating Codes and Traffic Monitoring, An adaptive heuristic algorithm for VLSI test vectors selection, A Parameterized Perspective on Packing Paths of Length Two, Locating-dominating sets and identifying codes in graphs of girth at least 5, Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems, Parameterizations of test cover with bounded test sizes
