| viXra.org > Combinatorics and Graph Theory > 2404 |
 |
 |
| viXra.org > Combinatorics and Graph Theory > 2404 |
|
|
[4] viXra:2404.0122 [pdf] submitted on 2024-04-25 17:40:35
Authors: Richard J. Mathar
Comments: 15 Pages.
A wazir is a fairy chess piece that attacks the 4 neighbors to the North, East, South and West of the chess board. This work constructs the bivariate generating functions for the number of placing w mutually non-attacking wazirs on rectangular boards of shape r X c at fixed c. The equinumerous setup counts binary {0,1}-arrays of dimension r X c which have w 1's with mutual L1 (Manhattan) distances > 1.
Category: Combinatorics and Graph Theory
[3] viXra:2404.0113 [pdf] replaced on 2024-05-19 07:17:18
Authors: Yasunori Ohto
Comments: 11 Pages.
The problem of determining whether a graph has a fixed-point-free automorphism is NP-complete. We demonstrate that the problem can be solved efficiently within polynomial time. First, we obtain the automorphisms of an input graph G by using a spectral method. Next, we prove the Theorem used to detect whether there is a fixed-point free automorphism in G. Next, we construct an algorithm to detect whether G has a fixed-point-free automorphism using this result. The computational complexity of detecting whether a graph has a fixed-point-free automorphism is O(n^5). If fixed-point-free automorphism exist, the computational complexity of obtaining a fixed-point-free automorphism is O(n^6). Then, the complexity classes P and NP are the same.
Category: Combinatorics and Graph Theory
[2] viXra:2404.0111 [pdf] replaced on 2024-05-19 07:19:54
Authors: Yasunori Ohto
Comments: 7 Pages.
We show that the graph isomorphism problem is solvable in polynomial time. First, we prove the theorem to obtain the automorphisms of G using eigenvalue sets. Next, we construct an algorithm to determine whether two given graphs G_a and G_b are isomorphic using this result. The computational complexity to detect whether the two graphs are isomorphic is O(n^6).
Category: Combinatorics and Graph Theory
[1] viXra:2404.0038 [pdf] submitted on 2024-04-07 22:15:55
Authors: Derrick Donkor
Comments: 9 Pages.
The proposed Particle Swarm Optimization (PSO) variant uses a search space with a non-overlapping distinct search space for each particle in the population in the exploration of the optimum solution. What is normally done for a reduction in swarm size and achieving a much quicker response in PSO is to manually set the swarm size and other auxiliary constants through trial and error. An algorithm is proposed which assigns each particle to a unique non-verlapping finite search space and aggregates all particles position to form the solution at every functional evaluation. This assignment of the particles to a finite distinct search space is suitable for quick convergence with less iteration and less particle size comparatively. The theoretical basis is provided for the proposed algorithm and empirical studies are conducted to compare the proposed algorithm with other selected optimization algorithms on reference benchmark test functions.
Category: Combinatorics and Graph Theory
| Third-Party Links: |
|