A greedy algorithm to construct covering arrays using a graph representation

DOI10.1016/J.INS.2018.10.048MaRDI QIDQ2201668zbMATH OpenOpenAlexWikidataFDO

Authors Jose Torres-Jimenez, Jose Carlos Perez-Torres

Publication date 29 September 2020

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2018.10.048

zbMATH Keywords

graphsgreedy algorithmscovering arraysminimum clique cover

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Covering arrays on graphs
• A greedy-metaheuristic 3-stage approach to construct covering arrays
• Covering analysis of the greedy algorithm for partial cover
• A survey of methods for constructing covering arrays
• An approximation algorithm for the total covering problem
• Publication:4484774
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Problems and algorithms for covering arrays via set covers
• scientific article; zbMATH DE number 3894490

Cites work

• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• A fast algorithm for the maximum clique problem
• A review on algorithms for maximum clique problems
• A survey of combinatorial testing
• An exact algorithm for the maximum clique problem
• An exact bit-parallel algorithm for the maximum clique problem
• An improved branch and bound algorithm for the maximum clique problem
• Constraint models for the covering test problem
• Construction of non-isomorphic covering arrays
• Covering arrays from cyclotomy
• Exhaustive Test Pattern Generation with Constant Weight Vectors
• Families of \(k\)-independent sets
• Orthogonal Arrays of Index Unity
• Products of mixed covering arrays of strength two
• Software and hardware testing using combinatorial covering suites
• Tower of covering arrays
• Two applications (for search theory and truth functions) of Sperner type theorems
• Upper bounds for covering arrays by tabu search.

Cited in

(1)

• A greedy-metaheuristic 3-stage approach to construct covering arrays

Describes a project that uses

Uses Software

• AETG
• MaxCliqueDyn

This page was built for publication: A greedy algorithm to construct covering arrays using a graph representation

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