Skip to Main content Skip to Navigation
Conference papers

Flooding Edge or Node Weighted Graphs

Abstract : This paper defines floodings on edge weighted and on node weighted graphs. Of particular interest are the highest floodings of a graph below a ceiling function defined on the nodes. It is shown that each flooding on a node weighted graph may be interpreted as a flooding on an edge weighted graphs with appropriate weights on the edges. The highest flooding of a graph under a ceiling function is then interpreted as a shortest distance on an augmented graph, using the ultrametric distance function. Thanks to this remark, the classical shortest distance algorithms may be used for constructing floodings.
Complete list of metadatas
Contributor : Bibliothèque Mines Paristech <>
Submitted on : Monday, June 17, 2013 - 10:33:12 AM
Last modification on : Wednesday, October 14, 2020 - 3:52:18 AM



Fernand Meyer. Flooding Edge or Node Weighted Graphs. 11th International Symposium, ISMM 2013, May 2013, Uppsala, Sweden. pp.341-352, ⟨10.1007/978-3-642-38294-9_29⟩. ⟨hal-00834695⟩



Record views