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

CRCW PRAMdivide-and-conquerline graphsreconstruction of a graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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

(12)

• Finding the root graph through minimum edge deletion
• Intersection graph of maximal stars
• scientific article; zbMATH DE number 4160789 (Why is no real title available?)
• scientific article; zbMATH DE number 140465 (Why is no real title available?)
• 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
• 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 dynamic algorithm for line graph recognition
• Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth
• ILIGRA: an efficient inverse line graph algorithm

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)