An efficient reconstruction of a graph from its line graph in parallel
From MaRDI portal
Publication:3201774
DOI10.1016/0196-6774(90)90034-CzbMath0715.68070MaRDI QIDQ3201774
Mark B. Novick, Joseph (Seffi) Naor
Publication date: 1990
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(90)90034-c
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
68W15: Distributed algorithms
Related Items
Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network, Edge intersection graphs of linear 3-uniform hypergraphs, Edge intersection graphs of linear 3-uniform hypergraphs, New results and open problems in line graphs, A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs, ILIGRA: an efficient inverse line graph algorithm, Finding the root graph through minimum edge deletion, Intersection graph of maximal stars