  Computing a graph prototype may constitute a core element for clustering or
classification tasks. However, its computation is an NP-Hard problem, even for
simple classes of graphs. In this paper, we propose an efficient approach based
on block coordinate descent to compute a generalized median graph from a set of
graphs. This approach relies on a clear definition of the optimization process
and handles labeling on both edges and nodes. This iterative process optimizes
the edit operations to perform on a graph alternatively on nodes and edges.
Several experiments on different datasets show the efficiency of our approach.
