We present a new deterministic algorithm to test constructively for isomorphism between two given finite-dimensional modules of a finitely generated algebra. The algorithm uses only basic field operations;for arbitrar...
详细信息
We present a new deterministic algorithm to test constructively for isomorphism between two given finite-dimensional modules of a finitely generated algebra. The algorithm uses only basic field operations;for arbitrary fields, this is not possible with the existing methodology. Furthermore, the number of field operations used by the algorithm is bounded by a polynomial in the length of the input. The algorithm has been implemented in the computer algebra system MAGMA and we report on its performance. Our approach has applications to other problems concerning decompositions of modules. (C) 2008 Elsevier Inc. All rights reserved.
The computation of Kronecker coefficients is a challenging problem with a variety of applications. In this paper we present an approach based on methods from symplectic geometry and residue calculus. We outline a gene...
详细信息
The computation of Kronecker coefficients is a challenging problem with a variety of applications. In this paper we present an approach based on methods from symplectic geometry and residue calculus. We outline a general algorithm for the problem and then illustrate its effectiveness in several interesting examples. Significantly, our algorithm does not only compute individual Kronecker coefficients, but also symbolic formulas that are valid on an entire polyhedral chamber. As a byproduct, we are able to compute several Hilbert series. (C) 2017 Elsevier Ltd. All rights reserved.
The 2-closure (G) over bar of a permutation group G on Omega is defined to be the largest permutation group on Omega, having the same orbits on Omega x Omega as G. It is proved that if G is supersolvable, then (G) ove...
详细信息
The 2-closure (G) over bar of a permutation group G on Omega is defined to be the largest permutation group on Omega, having the same orbits on Omega x Omega as G. It is proved that if G is supersolvable, then (G) over bar can be found in polynomialtime in vertical bar Omega vertical bar. As a by-product of our technique, it is shown that the composition factors of (G) over bar are cyclic or alternating.
Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation prob...
详细信息
Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation problem, assuming that the sought object forms a connected region in an intensity image. We show that the optimization problem of separating a connected region in a grid of M x N pixels is NP-hard under the interclass variance, a criterion that is often used in discriminant analysis. More importantly, we consider the basic case in which the object is bounded by two x-monotone curves (i.e., the object itself is x-monotone), and present polynomial-time algorithms for computing the optimal segmentation. Our main algorithm for exact optimal segmentation by two x-monotone curves runs in O(N-4) time;this algorithm is based on several techniques such as a parametric optimization formulation, a hand-probing algorithm for the convex hull of an unknown planar point set, and dynamic programming using fast matrix searching. Our efficient approximation scheme obtains an epsilon -approximate solution in O(epsilon N--1(2) log L) time, where epsilon is any fixed constant with 1 > epsilon > 0, and L is the total sum of the absolute values of the brightness levels of the image.
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which ...
详细信息
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e., finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs. (C) 2008 Elsevier B.V. All rights reserved.
作者：
Malyshev, D. S.Natl Res Univ
Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia
We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We a...
详细信息
We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We also present a complexity dichotomy for the problem and the family of all hereditary classes defined by forbidding an induced bull and any set of induced subgraphs each on at most 5 vertices.
Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respect...
详细信息
Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner point p, determine the optimal location of p and a triangulation of X boolean OR {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial- timealgorithm for this problem and then extend our solution to handle any constant number of Steiner points.
A net is a graph consisting of a triangle C and three more vertices, each of degree one and with its neighbour in C, and all adjacent to different vertices of C. We give a polynomial-time algorithm to test whether an ...
详细信息
A net is a graph consisting of a triangle C and three more vertices, each of degree one and with its neighbour in C, and all adjacent to different vertices of C. We give a polynomial-time algorithm to test whether an input graph has an induced subgraph which is a subdivision of a net. Unlike many similar questions, this does not seem to be solvable by an application of the "three-in-a-tree" subroutine. (C) 2013 Elsevier Inc. All rights reserved.
Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments...
详细信息
Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify all u-fp orthology assignments in a BMG. Simulations show that at least 75% of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs and not on any a priori knowledge about underlying gene or species trees.
A digraph H is infused in a digraph G if the vertices of H are mapped to vertices of G (not necessarily distinct), and the edges of H are mapped to edge-disjoint directed paths of G joining the corresponding pairs of ...
详细信息
A digraph H is infused in a digraph G if the vertices of H are mapped to vertices of G (not necessarily distinct), and the edges of H are mapped to edge-disjoint directed paths of G joining the corresponding pairs of vertices of G. The algorithmic problem of determining whether a fixed graph H can be infused in an input graph G is polynomial-time solvable for all graphs H (using paths instead of directed paths). However, the analogous problem in digraphs is NP-complete for most digraphs H. We provide a polynomial-time algorithm to solve a rooted version of the problem, for all digraphs H, in digraphs with independence number bounded by a fixed integer alpha. The problem that we solve is a generalization of the k edge-disjoint directed paths problem (for fixed k). (C) 2014 Elsevier Inc. All rights reserved.
暂无评论