The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This paper presents the first kinetic data structure (KDS) for maintenance of the Euclidean minimum spanning tree (EMST) on a set of n moving points in 2-dimensional space. We build a KDS of size O(n) in O(nlogn) preprocessing time by which their EMST is maintained efficiently during the motion. In terms of the KDS performance parameters, our KDS is responsive, local, and compact.
An n-Venn diagram consists of n curves drawn in the plane in such a way that each of the 2n possible intersections of the interiors and exteriors of the curves forms a connected non-empty region. A Venn diagram is convexly-drawable if it can be drawn with all curves convex and it is simple if at most two curves intersect at any point. A Venn diagram is called polar symmetric...
The Rand distance of two set partitions is the number of pairs {x,y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition. Let R(n,k) denote the number of distinct (unordered) pairs of partitions of n that have Rand distance k. For fixed k we prove that R(n,k) can be expressed as where...
We study the minimum number of label transitions around a given vertex v0 in a planar multigraph G in which the edges incident with v0 are labelled with integers 1, .…, l, where the minimum is taken over all embeddings of G in the plane. For a fixed number of labels, a linear-time FPT algorithm that (given the labels around v0) computes the minimum number of label...
We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular,...
The rotator graph has vertices labeled by the permutations of n in one line notation, and there is an arc from u to v if a prefix of u’s label can be rotated to obtain v’s label. In other words, it is the directed Cayley graph whose generators are $\sigma_{k} := (1 \ 2 \ \cdots \ k)$ for 2 ≤ k ≤ n and these rotations are applied to the indices of a permutation. In a restricted rotator graph the...
It is now common to add protein coding genes into cloning vectors for expression within non-native host organisms. Codon optimization supports translational efficiency of the desired protein product, by exchanging codons which are rarely found in the host organism with more frequently observed codons. Motif engineering, such as removal of restriction enzyme recognition sites or addition of immuno-stimulatory...
A coloring of edges of a finite directed graph turns the graph into a finite-state automaton. The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph of uniform outdegree (constant outdegree of any vertex) is synchronizing if the coloring turns the...
The guarding game is a game in which several cops has to guard a region in a (directed or undirected) graph against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, the robber on the remaining vertices (the robber-region). The goal of the robber is to enter the guarded region at a vertex...
We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in $\ensuremath{\mathcal{O}(B_{\ensuremath{\textit{tw}}+2}^2 \cdot \ensuremath{\textit{tw}}\ \cdot |V|)}$ time, where is the graph’s treewidth and the Bell numberBk is the number of partitions of a k-element set...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.