2/19/2023 0 Comments Unit disk graph![]() ![]() We would wait for the system to reach an equilibrium, which hopefully would minimize some potential function that measures the distance between our embedding and a unit disk graph. I have an idea but it's rather silly: I thought of running a physical simulation in which we place an attractive force on edges between vertices that are far apart, and a repelling force on non-edges between vertices that are close together. We present a data structure that maintains the. 67-90 to theunit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. "Low distortion Embeddings" is something related but different: There, the goal is that all edges should have similar lengths, whereas in my case I don't care about eliminating short edges. UD(S) of S has vertex set S and an edge between two sites s, t if and only if st 1. Has this type of thing been studied? In particular, I haven't been able to find an appropriate algorithm for the first item. Hopefully, if the embedding of $G$ is close to a unit disk graph, $A$ will return a good approximation to the $NP$-hard problem. Use the algorithm $A$ to find a solution for the graph.Of course, the resulting graph is probably not going to be a unit disk graph, but hopefully it is close to such a graph in some sense. Given a graph $G$, first embed it into the plane in such a way that vertex pairs connected by an edge tend to be close together, whereas vertex pairs that aren't connected tend to be farther apart.Let $A$ be an algorithm that solves an $NP$-hard problem in polynomial time in the special case of unit disk graphs. I am interested in designing approximation algorithms by adapting such algorithms to general graphs as follows: Some $NP$-hard problems become solvable in polynomial time for unit disk graphs. A UDG is therefore determined by the positions of nodes and a fixed common transmission range R. A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$. In the unit disk graph (UDG), two nodes communicate if and only if the distance between them is at most R, where R is the transmission radius which is equal for all nodes. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |