On the Complexity of Physical Problems and a Swarm Algorithm for k-Clique Search in Physical Graphs Academic Article uri icon


  • Abstract. As the complexity of systems increases, so does the need of examining the nature of complexity itself. This work discusses the domain of physical swarm problems, in which a swarm of mobile agents is employed for solving physical graph problems (where a certain amount of travel effort in required for every movement along the graph's edges). A new kind of complexity scheme, suitable for this domain, is discussed by examining a central problem of this domain—the physical k-clique problem. In this problem, a swarm comprising of …

publication date

  • November 1, 2005