Finding coherent cyclic orders in strong digraphs

A cyclic order in the vertex set of a digraph is said to be coherent if any arc is contained in a directed cycle whose winding number is one. This notion plays a key role in the proof by Bessy and Thomassé (2004) of a conjecture of Gallai (1964) on covering the vertex set by directed cycles. This paper presents an efficient algorithm for finding a coherent cyclic order in a strongly connected digraph, based on a theorem of Knuth (1974). With the aid of ear decomposition, the algorithm runs in O(nm) time, where n is the number of vertices and m is the number of arcs. This is as fast as testing if a given cyclic order is coherent.     

Polynomial time recognition and testing of isomorphism of cyclic tournaments

By a tournament is meant an oriented graph any pair of whose vertices is joined by precisely one directed edge; a tournament is cyclic if its automorphism group contains a permutation whose cyclic decomposition consists of a unique cycle containing all vertices. In the present paper we describe an algorithm for recognizing the isomorphism of cyclic tournaments. This algorithm has an arbitrary tournament as input. For this tournament, in polynomial time in the number of its vertices it determines its cyclicity, and when it is cyclic it constructs a canonical form for the tournament and generators of its automorphism group. A procedure which constructs the set of all nonconjugate Hamiltonian permutations for a given permutation group of odd order in polynomial time is of independent interest. The technique of construction of the basic algorithm uses both classical results of the theory of computational complexity with permutation groups and Schur's method of S-rings.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklovaa AN SSSR, Vol. 192, pp. 74–111, 1991.     

Finding minimum height elimination trees for interval graphs in polynomial time

The elimination tree plays an important role in many aspects of sparse matrix factorization. The height of the elimination tree presents a rough, but usually effective, measure of the time needed to perform parallel elimination. Finding orderings that produce low elimination is therefore important. As the problem of finding minimum height elimination tree orderings is NP-hard, it is interesting to concentrate on limited classes of graphs and find minimum height elimination trees for these efficiently. In this paper, we use clique trees to find an efficient algorithm for interval graphs which make an important subclass of chordal graphs. We first illustrate this method through an algorithm that finds minimum height elimination for chordal graphs. This algorithm, although of exponential time complexity, is conceptionally simple and leads to a polynomial-time algorithm for finding minimum height elimination trees for interval graphs.This work was supported by grants from the Norwegian Research Council.     

Isomorphic factorizations VIII: Bisectable trees

A tree is called even if its line set can be partitioned into two isomorphic subforests; it is bisectable if these forests are trees. The problem of deciding whether a given tree is even is known (Graham and Robinson) to be NP-hard. That for bisectability is now shown to have a polynomial time algorithm. This result is contained in the proof of a theorem which shows that if a treeS is bisectable then there is a unique treeT that accomplishes the bipartition. With the help of the uniqueness ofT and the observation that the bisection ofS into two copies ofT is unique up to isomorphism, we enumerate bisectable trees. Visiting Professor, University of Newcastle, 1976 and 1977 when this work was begun. Visiting Scholar, University of Michigan, 1981–82 on leave from Newcastle University (Australia) when this work was completed. The research was supported by grants from the Australian Research Grants Commission. The computing reported herein was performed by A. Nymeyer.     

Some results on the spectral reconstruction problem

This paper is concerned with the spectral version of the reconstruction conjecture: Whether a graph with n>2 vertices is determined (up to isomorphism) by the collection of its spectrum and the spectrum of its vertex-deleted graphs? Some positive results as well as a method for constructing counterexamples to the problem are provided.     

On 3-skein isomorphisms of graphs

It is shown that a 3-skein isomorphism between 3-connected graphs with at least 5 vertices is induced by an isomorphism. These graphs have no loops but may be infinite and have multiple edges.     

On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

Biembedding Steiner Triple Systems in Surfaces Using the Bose Construction

A uniform framework is presented for biembedding Steiner triple systems obtained from the Bose construction using a cyclic group of odd order, in both orientable and nonorientable surfaces. Within this framework, in the nonorientable case, a formula is given for the number of isomorphism classes and the particular biembedding of Ducrocq and Sterboul (preprint 18pp., 1978) is identified. In the orientable case, it is shown that the biembedding of Grannell et al. (J Combin Des 6 ( 7 ), 325–336) is, up to isomorphism, the unique biembedding of its type. Automorphism groups of the biembeddings are also given.     

Multiplicativity of acyclic local tournaments

A homomorphism of a digraph to another digraph is an edge-preserving vertex mapping. A digraphH is said to be multiplicative if the set of digraphs which do not admit a homomorphism toH is closed under categorical product. In this paper we discuss the multiplicativity of acyclic Hamiltonian digraphs, i.e., acyclic digraphs which contains a Hamiltonian path. As a consequence, we give a complete characterization of acyclic local tournaments with respect to multiplicativity.     

Accelerating method of global optimization for signomial geometric programming

Signomial geometric programming (SGP) has been an interesting problem for many authors recently. Many methods have been provided for finding locally optimal solutions of SGP, but little progress has been made for global optimization of SGP. In this paper we propose a new accelerating method for global optimization algorithm of SGP using a suitable deleting technique. This technique offers a possibility to cut away a large part of the currently investigated region in which the globally optimal solution of SGP does not exist, and can be seen as an accelerating device for global optimization algorithm of SGP problem. Compared with the method of Shen and Zhang [Global optimization of signomial geometric programming using linear relaxation, Appl. Math. Comput. 150 (2004) 99–114], numerical results show that the computational efficiency is improved obviously by using this new technique in the number of iterations, the required saving list length and the execution time of the algorithm.     

A linear-time algorithm for edge-disjoint paths in planar graphs

In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n ^5/3(loglogn)^1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability.     

Linear-time recognition of isomorphisms of tree-pictures

By tree-picture we mean image of a tree in the plane, and an isomorphism of tree-pictures is a coincidence of images up to an isotopy of the plane. An isomorphism is determined by local orientations of vertices, i.e., by a list of adjacent edges in clockwise order. A linear algorithm is given for finding a maximal word (in lexicographic order) in the alphabet of the natural numbers, equal to a given one up to a cyclic permutation. On the basis of this a linear algorithm is constructed for recognizing an isomorphism of tree-pictures.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 80–86, 1984.     

Birational maps between generalized Severi-Brauer varieties

A conjecture of Amitsur states that two Severi-Brauer varieties V(A) and V(B) are birationally isomorphic if and only if the underlying algebras A and B are the same degree and generate the same cyclic subgroup of the Brauer group. We examine the question of finding birational isomorphisms between generalized Severi-Brauer varieties. As a first step, we exhibit a birational isomorphism between the generalized Severi-Brauer variety of an algebra and its opposite. We also extend a theorem of P. Roquette to generalized Severi-Brauer varieties and use this to show that one may often reduce the problem of finding birational isomorphisms to the case where each of the separable subfields of the corresponding algebras are maximal, and therefore to the case where the algebras have prime power degree. We observe that this fact allows us to verify Amitsur’s conjecture for many particular cases.     

On weighted multiway cuts in trees

A min—max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min—max theorem does not apply to it.Corresponding author.Research of the author was supported by the A. v. Humboldt-Stiftung and the U.S. Office of Naval Research under the contract N-0014-91-J-1385.     

Obstructions for acyclic local tournament orientation completions

The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, including local tournaments. Local tournaments are intimately related to proper circular-arc graphs and proper interval graphs. In particular, proper interval graphs are precisely those which can be oriented as acyclic local tournaments. In this paper we determine all obstructions for acyclic local tournament orientation completions. These are in a sense minimal partially oriented graphs that cannot be completed to acyclic local tournaments. Our results imply that a polynomial time certifying algorithm exists for the acyclic local tournament orientation completion problem.     

Series-parallel graphs are windy postman perfect

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron O(G) induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if O(G) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win.     

On a matroid defined by ear-decompositions of graphs

A. Frank described in [1] an algorithm to determine the minimum number of edges in a graph G whose contraction leaves a factor-critical graph and he asked if there was an algorithm for the weighted version of the problem. We prove that the minimal critical-making edge-sets form the bases of a matroid and hence the matroid greedy algorithm gives rise to the desired algorithm.Partially supported by OTKA F014919, OTKA T17181 and OTKA T17580.     

On the isomorphism of commutative group algebras

LetG andH be finite abelian groups and letF be an arbitrary field. One fundamental problem is that of determining necessary and sufficient conditions for the isomorphism of the group algebrasFG andFH. No solution has appeared in the literature. Nevertheless by combining the results of Berman, Perlis and Walker, Cohen, and Deskins and providing connecting arguments a complete solution can be obtained. It is the purpose of this note to present such a solution.     

A method of linearizations for linearly constrained nonconvex nonsmooth minimization

A readily implementable algorithm is given for minimizing a (possibly nondifferentiable and nonconvex) locally Lipschitz continuous functionf subject to linear constraints. At each iteration a polyhedral approximation tof is constructed from a few previously computed subgradients and an aggregate subgradient, which accumulates the past subgradient information. This aproximation and the linear constraints generate constraints in the search direction finding subproblem that is a quadratic programming problem. Then a stepsize is found by an approximate line search. All the algorithm's accumulation points are stationary. Moreover, the algorithm converges whenf happens to be convex.