V. Kurlin
Computing braid groups of graphs with applications to robot motion planning
Kurlin, V.
Authors
Abstract
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.
Citation
Kurlin, V. (2012). Computing braid groups of graphs with applications to robot motion planning. Homology, Homotopy and Applications, 14(1), 159-180. https://doi.org/10.4310/hha.2012.v14.n1.a8
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 2012 |
Deposit Date | Oct 24, 2012 |
Publicly Available Date | Apr 9, 2013 |
Journal | Homology, Homotopy and Applications |
Print ISSN | 1532-0073 |
Electronic ISSN | 1532-0081 |
Publisher | International Press |
Peer Reviewed | Peer Reviewed |
Volume | 14 |
Issue | 1 |
Pages | 159-180 |
DOI | https://doi.org/10.4310/hha.2012.v14.n1.a8 |
Keywords | Graph, Braid group, Conguration space, Fundamental group, Homotopy type. |
Public URL | https://durham-repository.worktribe.com/output/1494707 |
Files
Published Journal Article
(249 Kb)
PDF
Copyright Statement
Copyright © International Press. First published in Homology, homotopy and applications, 14/1, 2012 published by International Press.
You might also like
Computing invariants of knotted graphs given by sequences of points in 3-dimensional space
(2017)
Presentation / Conference Contribution
A fast persistence-based segmentation of noisy 2D clouds with provable guarantees
(2015)
Journal Article
Relaxed disk packing
(2015)
Presentation / Conference Contribution
A Linear Time Algorithm for Visualizing Knotted Structures in 3 Pages
(2015)
Presentation / Conference Contribution