MathOverflow Asked by Manfred Weis on January 17, 2021
Given $K_n$ with weighted edges, we can fix an edge $e_{AB}$, iterate over all non-adjacent edges $e_{CD}in Esetminus e_{AD}$ and record how often $e_{AB}$ was in the lightest, intermediate or heaviest perfect matching of the subgraph induced by the the set $lbrace A,B,C,Drbrace$ of the pair’s adjacent vertices.
That procedure yields a vector of three values $(r,g,b), r+g+b = binom{n-2}{2}$ for every edge and can thus be interpreted as planar barycentric coordinates of the edges.
It is clear that these coordinates do not depend on changes to vertex weights and may thus provide a characterization of instances of combinatorial optimzation problems that also exhibit that independence from vertex weights; the Traveling Salesman Problem is prototypical in that respect.
Question:
have these barycentric coordinates of weighted edges already been mentioned or investigated w.r.t. usability for e.g. data analysis?
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP