Path Algorithms on Regular Graphs

Didier Caucal (1) , Trong Hieu Dinh (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We consider standard algorithms of finite graph theory, like for instance shortest path algorithms. We present two general methods to polynomially extend these algorithms to infinite graphs generated by deterministic graph grammars.

Domaines: Algorithme et structure de données [cs.DS]

Didier Caucal, Trong Hieu Dinh. Path Algorithms on Regular Graphs. FCT'07, Aug 2007, Budapest, Hungary. pp.199-212, ⟨10.1007/978-3-540-74240-1_18⟩. ⟨hal-00620155⟩