0
$\begingroup$

I have by accident found an interesting kind of spanner of complete symmetric graphs $G(V,E)$ with weighted edges.
What I actually had planned was to implement an algorithm for calculating certain non-optimal edges of TSP instances, but due to a bug I had actually calculated the set $\lbrace a,b \rbrace$ of edges with the property that for $\forall c\in E\setminus\lbrace a,b\rbrace:\ \exists d\in E\setminus\lbrace a,b,c\rbrace\ $ s.t. $\ \omega_{ab}+\omega_{cd}\le\omega_{ac}+\omega_{bd}\,\land\,\omega_{ab}+\omega_{cd}\le\omega_{ad}+\omega_{bc}$, i.e. for every vertex $c$ that is not adjacent to such an edge we can find another non-adjacent vertex $d$ such that the edges $\lbrace a,b\rbrace$ and $\lbrace c,d\rbrace$ resemble the minimum weight perfect matching of the subgraph induced by vertices $a,b,c,d$

Visualization of the K4 matching edges

The resulting graph is "almost" biconnected and may serve as the basis for shape hulls or partitioning of point sets. crossing pairs of edges are colored blue and the other, two-optimal subset of edges is depicted in yellow.

Question:

have spanning subgraphs that are defined by the edges of certain $K_4$ matchings already been investigated, resp. can anything be said about their properties?

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean by spanner? $\endgroup$
    – Gerry Myerson
    Commented Feb 23, 2021 at 23:14
  • $\begingroup$ @GerryMyerson I meant it to be an abbreviation for spanning subgraph, i.e. a subgraph that contains all vertices of the original graph. If that abbreviation isn't appropriate I will replace it in an edit; any suggestions? $\endgroup$
    – Manfred Weis
    Commented Feb 24, 2021 at 3:57
  • 1
    $\begingroup$ I suggest just calling it a spanning subgraph. $\endgroup$
    – Gerry Myerson
    Commented Feb 24, 2021 at 5:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .