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

DOI10.7155/JGAA.00522MaRDI QIDQ5119373zbMATH OpenOpenAlexFDO

Authors Wilfried Ehounou, Arnaud de Moissac, Dimitri Watel, Marc-Antoine Weisser, D. Barth

Publication date 4 September 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

heuristicNP-completenesselectrical networksline-graph

Mathematics Subject Classification ID

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

Recommendations

• Some inverse optimization problems under the Hamming distance
• Improvement of shortest path of arborescent network in the case of Hamming distance
• Electrical flows over spanning trees
• Methods to search for configurations of distribution networks
• Network design for minimum spanning trees under Hamming distance

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 2117218 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• An efficient reconstruction of a graph from its line graph in parallel
• ILIGRA: an efficient inverse line graph algorithm
• Listing all maximal cliques in sparse graphs in near-optimal time
• Node-and edge-deletion NP-complete problems

Cited in

(1)

• Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth

Describes a project that uses

Uses Software

• ILIGRA

This page was built for publication: Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network

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