Hardness results for covering arrays avoiding forbidden edges and error-locating arrays

DOI10.1016/j.tcs.2011.07.010zbMath1228.68031OpenAlexW2084172672MaRDI QIDQ650881

Lucia Moura, Elizabeth Maltais

Publication date: 7 December 2011

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.010

zbMATH Keywords

NP-completenesssoftware testinghardness of approximationcovering arraysedge clique coverserror-locating arraysforbidden interactionshardware testing

Mathematics Subject Classification ID

Fault detection; testing in circuits and networks (94C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items

A primer on the application of neural networks to covering array generation ⋮ Sliced AETG: a memory-efficient variant of the AETG covering array generation algorithm ⋮ Arrays for combinatorial interaction testing: a review on constructive approaches ⋮ A survey on the problems and algorithms for covering arrays via set covers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple lower bound on edge coverings by cliques
• Covering arrays avoiding forbidden edges
• On clique covers and independence numbers of graphs
• Problems and algorithms for covering arrays
• Sperner capacities
• A survey of combinatorial testing
• Locating Errors Using ELAs, Covering Arrays, and Adaptive Testing Algorithms
• Finding the Best CAFE Is NP-Hard
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• On the hardness of approximating minimization problems
• The Representation of a Graph by Set Intersections