作者：
Zabudsky, G.G.Siberian Division
Sobolev Institute of Mathematics Russian Academy of Sciences Omsk 644099 ul. Pevtsova 13 Russian Federation
Optimal location of interconnected facilities on tree networks is considered in the case when some of the nodes of the network contain existing facilities. The distances between the facilities must satisfy maximum con...
详细信息
In this paper, we introduce new algorithms for selecting taxon samples from large evolutionary trees, maintaining uniformity and randomness, under certain new constraints on the taxa. The algorithms are efficient as t...
详细信息
ISBN:
(纸本)9781424400379
In this paper, we introduce new algorithms for selecting taxon samples from large evolutionary trees, maintaining uniformity and randomness, under certain new constraints on the taxa. The algorithms are efficient as their runtimes and space complexities are polynomial. The algorithms have direct applications to the evolution of phylogenetic tree and efficient supertree construction using biologically curated data. We also present new lower bounds for the problem of constructing evolutionary tree from experiment under some earlier stated constraints. All the algorithms have been implemented
We deal with different algorithmic questions regarding properly arc-colored s-t paths, trails and circuits in arc-colored digraphs. Given an arc-colored digraph D-c with c >= 2 colors, we show that the problem of m...
详细信息
ISBN:
(纸本)9783642135613
We deal with different algorithmic questions regarding properly arc-colored s-t paths, trails and circuits in arc-colored digraphs. Given an arc-colored digraph D-c with c >= 2 colors, we show that the problem of maximizing the number of arc disjoint properly arc-colored s-t trails can be solved in polynomial time. Surprisingly, we prove that the determination of one properly arc-colored s-t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c = Omega(n), where n denotes the number of vertices in D-c. If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex x (resp., properly arc-colored Hamiltonian s-t path) is NP-complete, even if c = 2. As a consequence, we solve a weak version of an open problem posed in Gutin et. al. [17].
In the current paper, we present two polynomial algorithms for constructing relatively small strongly admissible labellings, with associated min-max numberings, for a particular argument. These labellings can be used ...
详细信息
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and t...
详细信息
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m(omega) n), where omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. We exhibit an O(m(2)n + mn(2)) algorithm. When the edge weights are integers, we have an O(m(2)n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m(omega)) time. For any epsilon > 0, we also design an 1+epsilon approximation algorithm. The running time of this algorithm is O((m(omega)/epsilon)log(W/epsilon)) for reasonably dense graphs, where W is the largest edge weight.
In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different verti...
详细信息
In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N-6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this work.
This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear ...
详细信息
This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities. The central notion is that of a 3-edge cutset, namely, a set of 3 edges that, when removed, disconnects the graph. Conversely, our approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the traveling salesman problem. The approach is illustrated on two examples, Halin graphs and prismatic graphs.
暂无评论