ﻻ يوجد ملخص باللغة العربية
We describe a technique to reorganize topologies of Steiner trees by exchanging neighbors of adjacent Steiner points. We explain how to use the systematic way of building trees, and therefore topologies, to find the correct topology after nodes have been exchanged. Topology reorganizations can be inserted into the enumeration scheme commonly used by exact algorithms for the Euclidean Steiner tree problem in $d$-space, providing a method of improvement different than the usual approaches. As an example, we show how topology reorganizations can be used to dynamically change the exploration of the usual branch-and-bound tree when two Steiner points collide during the optimization process. We also turn our attention to the erroneous use of a pre-optimization lower bound in the original algorithm and give an example to confirm its usage is incorrect. In order to provide numerical results on correct solutions, we use planar equilateral points to quickly compute this lower bound, even in dimensions higher than two. Finally, we describe planar twin trees, identical trees yielded by different topologies, whose generalization to higher dimensions could open a new way of building Steiner trees.
In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of emph{terminals} $Tsubseteq V$, the objective is to find a minimum-cost tree $E subseteq E$ that spans the terminals. The p
We consider a natural variant of the well-known Feedback Vertex Set problem, namely the problem of deleting a small subset of vertices or edges to a full binary tree. This version of the problem is motivated by real-world scenarios that are best modeled by full binary trees. We establish that bo
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line
Among other results, we prove the following theorem about Steiner minimal trees in $d$-dimensional Euclidean space: if two finite sets in $mathbb{R}^d$ have unique and combinatorially equivalent Steiner minimal trees, then there is a homotopy between
Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problems such as subgraph isomorphism