Geodesic
Computing braid groups of graphs with applications to robot motion planning
Homology, homotopy, and applications, Tome 14 (2012) no. 1, pp. 159-180.

Voir la notice de l'article provenant de la source International Press of Boston

An algorithm is designed to write down presentations of graph braid groups. Generators are represented in terms of actual motions of robots moving without collisions on a given connected graph. A key ingredient is a new motion planning algorithm whose complexity is linear in the number of edges and is quadratic in the number of robots. The computing algorithm implies that 2-point braid groups of all light planar graphs have presentations where all relators are commutators.
DOI : 10.4310/HHA.2012.v14.n1.a8
Classification : 05C25, 20F36, 57M05
Keywords: graph, braid group, configuration space, fundamental group, homotopy type, deformation retraction, collision free motion, planning algorithm, complexity, robotics 
@article{HHA_2012_14_1_a8,
     author = {Vitaliy Kurlin},
     title = {Computing braid groups of graphs with applications to robot motion planning},
     journal = {Homology, homotopy, and applications},
     pages = {159--180},
     publisher = {mathdoc},
     volume = {14},
     number = {1},
     year = {2012},
     doi = {10.4310/HHA.2012.v14.n1.a8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4310/HHA.2012.v14.n1.a8/}
}
TY  - JOUR
AU  - Vitaliy Kurlin
TI  - Computing braid groups of graphs with applications to robot motion planning
JO  - Homology, homotopy, and applications
PY  - 2012
SP  - 159
EP  - 180
VL  - 14
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4310/HHA.2012.v14.n1.a8/
DO  - 10.4310/HHA.2012.v14.n1.a8
LA  - en
ID  - HHA_2012_14_1_a8
ER  - 
%0 Journal Article
%A Vitaliy Kurlin
%T Computing braid groups of graphs with applications to robot motion planning
%J Homology, homotopy, and applications
%D 2012
%P 159-180
%V 14
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4310/HHA.2012.v14.n1.a8/
%R 10.4310/HHA.2012.v14.n1.a8
%G en
%F HHA_2012_14_1_a8
Vitaliy Kurlin. Computing braid groups of graphs with applications to robot motion planning. Homology, homotopy, and applications, Tome 14 (2012) no. 1, pp. 159-180. doi : 10.4310/HHA.2012.v14.n1.a8. http://geodesic.mathdoc.fr/articles/10.4310/HHA.2012.v14.n1.a8/

Cité par Sources :