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

DOI10.1016/0196-6774(90)90034-CMaRDI QIDQ3201774zbMATH OpenOpenAlexFDO

Authors Joseph (Seffi) Naor, Mark B. Novick

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)

Recommendations

• scientific article; zbMATH DE number 140465
• Parallel Algorithm for Cograph Recognition with Applications
• scientific article; zbMATH DE number 4160789
• ILIGRA: an efficient inverse line graph algorithm
• Parallel recognition of complement reducible graphs and cotree construction

Cited in

(11)

• ILIGRA: an efficient inverse line graph algorithm
• scientific article; zbMATH DE number 4160789 (Why is no real title available?)
• Intersection graph of maximal stars
• Finding the root graph through minimum edge deletion
• Edge intersection graphs of linear 3-uniform hypergraphs
• scientific article; zbMATH DE number 140465 (Why is no real title available?)
• 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
• A dynamic algorithm for line graph recognition
• Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3201774)