Affiliations: Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic. pavel.surynek@mff.cuni.cz | Department of Mathematics Education, Faculty of Mathematics and Physics, Charles University in Prague, Sokolovská 83, 186 75 Praha 8, Czech Republic. petra.surynkova@mff.cuni.cz | Faculty of Mathematics and Physics, Charles University in Prague, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic. miloschromy@gmail.com
Note: [] This work is supported by the Czech Science Foundation under the contract number GAP103/10/1287 and by Charles University in Prague within the PRVOUK project (section P46). Address for correspondence: Charles University in Prague, Faculty of Mathematics and Physics, Malostranské náměstí 25, 11800 Praha, Czech Republic
Abstract: This paper proposes a framework for analyzing algorithms for inductive processing of bi-connected graphs. The BIBOX algorithm for solving cooperative path-finding problems over bi-connected graphs is submitted for the suggested analysis. The algorithm proceeds according to a decomposition of a given bi-connected graph into handles. After finishing a handle, the handle is ruled out of consideration and the processing task is reduced to a task of the same type on a smaller graph. The handle decomposition for which the BIBOX algorithm performs best is theoretically identified. The conducted experimental evaluation confirms that the suggested theoretical analysis well corresponds to the real situation.
