An efficient reconstruction of a graph from its line graph in parallel
Joseph Seffi Naor, Mark B. Novick · Journal of Algorithms · 1990
Let G = (V, E) denote a line graph. An O(log∥V∥) parallel reconstruction of root graphs from line graphs is presented that uses O(∥E∥) processors in the CRCW model. It is based on a divide-and-conquer scheme that partitions the line graph into two sets, such that each set induces a connected subgraph. Previously known algorithms of the same complexity used a large (though polynomial) number of processors. The algorithm is optimal up to a logarithmic factor.