An efficient reconstruction of a graph from its line graph in parallel

DOI10.1016/0196-6774(90)90034-CzbMath0715.68070OpenAlexW1998050844MaRDI 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

zbMATH Keywords

line graphsdivide-and-conquerCRCW PRAMreconstruction of a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distributed algorithms (68W15)

Related Items (9)

ILIGRA: an efficient inverse line graph algorithm ⋮ New results and open problems in line graphs ⋮ A dynamic algorithm for line graph recognition ⋮ Intersection graph of maximal stars ⋮ Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network ⋮ 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 ⋮ Edge intersection graphs of linear 3-uniform hypergraphs ⋮ Edge intersection graphs of linear 3-uniform hypergraphs ⋮ Finding the root graph through minimum edge deletion

This page was built for publication: An efficient reconstruction of a graph from its line graph in parallel