The complexity of Boolean failure identification

DOI10.1016/J.TCS.2025.115536MaRDI QIDQ6903530zbMATH OpenFDO

Authors Nicola Galesi, Fariba Ranjbar

Publication date 10 November 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

group testingNP-hardnessBoolean network tomographyBoolean failure identification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation algorithms for NP-hard problems.
• Network Tomography of Binary Network Performance Characteristics
• New Turán Exponents for Two Extremal Hypergraph Problems
• Structure preserving reductions among convex optimization problems
• Tight bounds to localize failure nodes on trees, grids and through embeddings under Boolean network tomography
• Union-free families of sets and equations over fields
• Vertex-connectivity for node failure identification in Boolean network tomography
• Vertex-connectivity for node failure identification in Boolean network tomography

This page was built for publication: The complexity of Boolean failure identification

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