2012/01/19 by Víctor Álvarez, Álvarez, Víctor, Armario, José-Andrés +9
Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1201.4021
openalex publication_date 2012/01/19 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Three algorithms looking for pretty large partial Hadamard matrices are described. Here "large" means that hopefully about a third of a Hadamard matrix (which is the best asymptotic result known so far, [dLa00]) is achieved. The first one performs some kind of local exhaustive search, and consequently is expensive from the time consuming point of view. The second one comes from the adaptation of the best genetic algorithm known so far searching for cliques in a graph, due to Singh and Gupta [SG06]. The last one consists in another heuristic search, which prioritizes the required processing time better than the final size of the partial Hadamard matrix to be obtained. In all cases, the key idea is characterizing the adjacency properties of vertices in a particular subgraph Gt of Ito's Hadamard Graph Delta (4t) [Ito85], since cliques of order m in Gt can be seen as (m+3)*4t partial Hadamard matrices.