Optimal Graph Joining with Applications to Isomorphism Detection and Identification

Phuong N. Hoàng* and Kevin McGoff and Andrew B. Nobel and Yang Xiang and Bongsoo Yi · 2025

Read Optimal Graph Joining with Applications to Isomorphism Detection and Identification by Phuong N. Hoàng* and Kevin McGoff and Andrew B. Nobel and Yang Xiang and Bongsoo Yi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14862.txt.

Introduction

Phuong N. Hoàng, Kevin McGoff, and three co-authors propose a transport-based way to compare networks. Their joining of two graphs glues them into one product graph that keeps each graph's degree structure intact. The cheapest joining, under a cost for matching vertex labels, gives a distance-like score between the two networks.

That best joining problem turns out to be a linear program with a well-shaped solution set. The authors prove basic properties and tie the problem to the famous graph isomorphism question, working out when families of graphs can be told apart this way. The method offers a principled tool for fingerprinting networks in chemistry, biology, and security.

Catalog record

CREATORPhuong N. Hoàng* and Kevin McGoff and Andrew B. Nobel and Yang Xiang and Bongsoo Yi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE172 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14862

Browse the full library · About the Tower of Babel