Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network

DOI10.7155/jgaa.00522zbMath1447.05069OpenAlexW3010783666MaRDI QIDQ5119373

Wilfried Ehounou, Dimitri Watel, Marc-Antoine Weisser, Arnaud de Moissac, Dominique Barith

Publication date: 4 September 2020

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00522

zbMATH Keywords

NP-completenessheuristicelectrical networksline-graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Uses Software

• ILIGRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• ILIGRA: an efficient inverse line graph algorithm
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• An efficient reconstruction of a graph from its line graph in parallel
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Node-and edge-deletion NP-complete problems