Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

The transitive closure of a random digraph

In a random n-vertex digraph, each arc is present with probability p, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when n is large and np is equal to a constant c greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ₂n vertices, where Θ is the unique root in [0, 1] of the equation 1 ? x ? e^?ex = 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time O(n). for all choices of n and p, the expected execution time of the algorithm is O(w(n) (n log n)^4/3), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω(n²) the algorithm presents the transitive closure in the compact form (A × B)U C, where A and B are sets of vertices, and C is a set of arcs.     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Lower bounds for Turán's problem

Turán's problem is to determine the maximum numberT(n,k,t) oft-element subsets of ann-set without a complete sub-hypergraph onk vertices, i.e., allt-subsets of ak-set. It is proved that fora≥1 fixed andt sufficiently largeT(n, t+a,t)>(1-a(a+4+o(1))logt/( _a ^t )( _t ⁿ holds     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

Rado Numbers fora(x+y)=bz

In the case of existence the smallest numberN=Ra_kis called a Rado number if it is guaranteed that anyk-coloring of the numbers 1, 2, …, Ncontains a monochromatic solution of a given system of linear equations. We will determine Ra_k(a, b) for the equationa(x+y)=bzifb=2 andb=a+1. Also, the case of monochromatic sequences {x_n} generated bya(x_n+x_n+1)=bx_n+2 is discussed.     

An algorithm for the enumeration of spanning trees

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.     

Nonhomogeneous recursions and Generalised Continued Fractions

Consider the (n+1)st order nonhomogeneous recursionX _k+n+1=b _k X _k+n +a _k ⁽ⁿ⁾ X _k+n-1+...+a _k ⁽¹⁾ X _k +X _k .Leth be a particular solution, andf ⁽¹⁾,...,f ⁽ⁿ⁾,g independent solutions of the associated homogeneous equation. It is supposed thatg dominatesf ⁽¹⁾,...,f ⁽ⁿ⁾ andh. If we want to calculate a solutiony which is dominated byg, but dominatesf ⁽¹⁾,...,f ⁽ⁿ⁾, then forward and backward recursion are numerically unstable. A stable algorithm is derived if we use results constituting a link between Generalised Continued Fractions and Recursion Relations.     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

An algorithm for the determination of longest distances in a graph

This paper presents an algorithm for ranking the vertices of a directed graph. Its space and time requirements are bounded byc ₁ n ² +c ₂, wheren is the number of vertices of the graph andc ₁,c ₂ are positive constants which are independent of the size or other properties of the graph.The algorithm can be easily modified to solve the problem of determining longest distances from a vertex to all other vertices in a positive real valued graph with at mostc ₁ n ² +c ₂ elementary operations; the same result holds for shortest distances in negative real valued graphs.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

On the Growth of Positive Definite Double Sequences Which Are not Moment Sequences

For every a > 1, there is a function f : N²₀ → R, which is positive semidefinite but not a moment sequence, such that |f(m, n)| ≥ m+ n^a(m+n) for all (m, n). The constant 1 is the best possible.     

Computing solutions for matching games

A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting w: E? \mathbb R₊{w: E\to {\mathbb R}_+}. The player set is N and the value of a coalition S í N{S \subseteq N} is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n ² log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in O(n ⁴) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.     

Lie-admissible algebras and generalized witt algebras ∗

The symmetric group 𝔖_n+1 of degree n + 1 admits an n-dimensional irreducible Q𝔖_n-module V corresponding to the hook partition (2, 1^n?1). By the work of Craig and Plesken, we know that there are σ(n + 1) many isomorphism classes of Z𝔖_n+1-lattices which are rationally equivalent to V, where σ denotes the divisor counting function. In the present article, we explicitly compute the Solomon zeta function of these lattices. As an application we obtain the Solomon zeta function of the Z𝔖_n+1-lattice defined by the Specht basis.     

Polynomial auction algorithms for shortest paths

In this paper we consider strongly polynomial variations of the auction algorithm for the single origin/many destinations shortest path problem. These variations are based on the idea of graph reduction, that is, deleting unnecessary arcs of the graph by using certain bounds naturally obtained in the course of the algorithm. We study the structure of the reduced graph and we exploit this structure to obtain algorithms withO (n min{m, n logn}) andO(n ²) running time. Our computational experiments show that these algorithms outperform their closest competitors on randomly generated dense all destinations problems, and on a broad variety of few destination problems.Research supported by NSF under Grant No. DDM-8903385, by the ARO under Grant DAAL03-86-K-0171, by a CNR-GNIM grant, and by a Fullbright grant     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Note on the solution of a certain boundary-value problem

A simple algorithm is described for inverting the operatorD _x D _y (D _x andD _y here and subsequently denote partial differentiation with respect tox andy respectively) which occurs in the iterative solution of the equationD _x D _y f (x, y)=g (x, y, f, D _x f, D _x ² f,D _x D _y f, D _y ² f) when boundary values off(x,y) are given along the sides of the rectangle in thexy-plane whose corners are at the points (a,b); (a+(n+1)k,b); (a+(n+1)k,b+(n+1)h); (a,b+(n+1)h).Communication M. R. 43 of the Computation Department of the Mathematical Centre, Amsterdam.     

Reduktion von Präzedenzstrukturen

Zusammenfassung Es wird zunächst der Begriff des (transitiv) irreduziblen KernsG _* eines gerichteten GraphenG eingeführt und einige Eigenschaften von irreduziblen Kernen hergeleitet. — Es wird insbesondere gezeigt, daß mit höchstens 0(n ³) elementaren Rechenoperationen die Bestimmung eines Kernes eines beliebigen gerichteten Graphen mitn Ecken möglich ist. — Für Ablaufprobleme zeigt dieses Resultat, daß höchstens 0(n ³) Operationen notwendig sind, um alle redundanten Nebenbedingungen zu eliminieren.

---

Summary A (transitive) irreducible kernelG _* of a directed graphG is introduced as a partial graph ofG, which has the same transitive closure asG while no proper subgraph ofG _* has this property. — The author shows that at most 0(n ³) elementary operations are necessary to obtain a kernel of an arbitrary graph wheren is the number of vertices ofG. In the case of scheduling problems this result shows that at most 0(n ³) operations are needed to eliminate all redundant constraints.