103,076 research outputs found
Modification of Edmonds' maximum matching algorithm
No full textEdmonds developed an efficient algorithm for finding in a given graph G a matching of maximum cardinality. This algorithm 'shrinks' parts of the graph G. Although helpful to the intuitive understanding of the theory, shrinking is compl cated to implement on an electronic computer. The modification presented in this paper avoids shrinking. It employs instead a treelike arrangement of alternating paths. The possibility of such an arrangement is also of theoretical interest, and it s proof forms the main part of the paper
On matrices with the Edmonds-Johnson property
No full textThe strong Chvátal rank of a rational matrix A is the smallest number t such that the polyhedron defined by the system b <= A x <= c, l <= x <= u has Chvátal rank at most t for all integral vectors b,c,l,u. Matrices with strong Chvátal rank at most 1 are said to have the Edmonds-Johnson property. There are two main classes of matrices known to have the Edmonds-Johnson property, one was introduced by Edmonds and Johnson, and the other by Gerards and Schrijver.
Characterizing integral matrices with the Edmonds-Johnson property seems complicated. However, Gerards and Schrijver noticed that there are some openings if we restrict ourselves to totally half-modular matrices, and they conjectured a characterization of totally half-modular matrices with the Edmonds-Johnson property. In this thesis we introduce two new classes of totally half-modular matrices with the Edmonds-Johnson property, that prove the validity of the conjecture by Gerards and Schrijver in two particular cases.
In Chapter 3 we study systems of the from b <= Mx <= d, l <= x <= u, where M is obtained from a totally unimodular matrix with two nonzero elements per row by multiplying by 2 some of its columns, and b,d,l,u are integral vectors. We give an explicit description of a totally dual integral system that describes the integer hull of the polyhedron P defined by the above inequalities. Since the inequalities of such totally dual integral system are Chvátal inequalities for P, our result implies that the matrix M has the Edmonds-Johnson property.
In Chapter 4 we consider the class of totally half-modular matrices obtained from matrices 0, ± 1 with at most two nonzero entries per column by multiplying by 2 some of the columns. In this class we characterize, in terms of excluded minors, the matrices that have the Edmonds-Johnson property.Il rango forte di Chvátal di una matrice razionale A è il più piccolo numero t tale che il poliedro definito dal sistema b <= A x <= c, l <= x <= u ha rango di Chvátal al più t per tutti i vettori interi b,c,l,u. Matrici con rango forte di Chvátal al più 1 si dicono avere la proprietà di Edmonds-Johnson. Ci sono due principali classi note di matrici con la proprietà di Edmonds-Johnson, una fu introdotta da Edmonds e Johnson, e l'altra da Gerards e Schrijver.
Caratterizzare le matrici intere con la proprietà di Edmonds-Johnson sembra complicato. Tuttavia, Gerards e Schrijver notarono che ci sono più possibilità se ci restringiamo alle matrici totalmente 1/2-modulari, e congetturarono una caratterizzazione delle matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson. In questa tesi introduciamo due nuovi classi di matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson, che provano la validità della congettura di Gerards e Schrijver in due casi particolari.
Nel Capitolo 3 studiamo sistemi nella forma b <= Mx <= d, l <= x <= u, dove M è ottenuta da una matrice totalmente unimodulare con due elementi diversi da zero per riga moltiplicando per 2 alcune colonne, e b,d,l,u sono vettori interi. Noi diamo una descrizione esplicita di un sistema totally dual integral che descrive l'inviluppo convesso dei punti interi del poliedro P definito dalle disuguaglianze precedenti. Dato che le disuguaglianze di tale sistema totally dual integral sono disuguaglianze di Chvátal per P, questo implica che la matrice M ha la proprietà di Edmonds-Johnson.
Nel Capitolo 4 consideriamo la classe delle matrici totalmente 1/2-modulari ottenute da matrici 0, ± 1 con al più due elementi non zero per colonna moltiplicando per 2 alcune colonne. In questa classe caratterizziamo, in termini di minori esclusi, le matrici che hanno la proprietà di Edmonds-Johnson
A Dedication to Thomas A. Edmonds
No full textA dedication of the University of Richmond Law Review issue to outgoing Dean Thomas A. Edmonds who served as Dean from 1977 until 1987
Exponentiality of the exchange algorithm for finding another room-partitioning
No full textLet T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange algorithm walks from room to room until it finds a second different room-partitioning R′. In fact, this algorithm generalizes the Lemke-Howson algorithm for finding a Nash equilibrium for two-person games. In this paper, we show that the running time of the exchange algorithm is not polynomial relative to the number of rooms, by constructing a sequence of (planar) instances, in which the algorithm walks from room to room an exponential number of times. We also show a similar result for the problem of finding a second perfect matching in Eulerian graphs. © 2012 Elsevier B.V. All rights reserved
Letter, [Author unclear] to Paulina T. Merritt
No full textHandwritten letter to Paulina Merritt from an unknown author, October 1, 1876.
Distribution and biology of the rare scarab beetle Megatharsis buckleyi Waterhouse, 1891 (Coleoptera: Scarabaeinae: Phanaeini)
No full textGillett, Conrad P. D. T., Edmonds, W. D., Villamarin, Santiago (2009): Distribution and biology of the rare scarab beetle Megatharsis buckleyi Waterhouse, 1891 (Coleoptera: Scarabaeinae: Phanaeini). Insecta Mundi 2009 (80): 1-8, DOI: 10.5281/zenodo.540507
On finding another room-partitioning of the vertices
No full textLet T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning of T is a subset R of the rooms such that each vertex of T is in exactly one room in R. We prove that if T has a room-partitioning R, then there is another room-partitioning of T which is different from R. The proof is a simple algorithm which walks from room to room, which however we show to be exponential by constructing a sequence of (planar) instances, where the algorithm walks from room to room an exponential number of times relative to the number of rooms in the instance. We unify the above theorem with Nash’s theorem stating that a 2-person game has an equilibrium, by proving a combinatorially simple common generalization
MATRICES WITH THE EDMONDS-JOHNSON PROPERTY
No full textA matrix A = (a~j) has the Edmonds-Johnson property if, for each choice of integral vectors dl, d,., b~, b~, the convex hull of the integral solutions of dt~-x~-d2, bt~-Ax~-b. ~ is obtained by adding the inequalities cx~_[~], where c is an integral vector and cx~_J holds for each solution of da~_x~_d2, b~_Ax~_b.. We characterize the Edmonds-Johnson property for integral mat-rices A which satisfy S la~j[-~2 for each (row index) i. A corollary is that if G is an undirected graph which does not contain any homomorph of/(4 in which all triangles of/(4 have become odd circuits, then G is t-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry
Tight Lower Bounds for st-Connectivity on the NNJAG Model
No full textDirected st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a time-space lower bound on the probabilistic NNJAG model of Poon [Poo93]. Let n be the number of nodes in the input graph and S, T be the space and time used by the NNJAG, respectively. We show that for any ffi ? 0 if an NNJAG uses space S 2 O(n 1\Gammaffi ) then T 2 2\Omega\Gamma629 2 (n=S)) , otherwise T 2 2 \Omega\Gamma677 2 ( n log n S )= log log n) \Theta (nS= log n) 1=2 . (In a preliminary version of this paper by Edmonds and Poon [EP95], a lower bound of T 2 2\Omega\Gamma314 2 ( n log n S )= log log n) \Theta (nS= log n) 1=2 was proved.) Our result greatly improves the previous lower bound of ST 2 \Omega\Gamma n 2 = log n) on the JAG model by Barnes and Edmonds [BE93] and that of S 1=3 T 2 \Omega\Gamma n 4=3 ) on the NNJAG model by Edmonds [Edm93a]. Our lower bound is tight for S 2 O(n ..
Themiste (Lagenopsis) cymodoceae Edmonds 1956
No full textThemiste (Lagenopsis) cymodoceae (Edmonds, 1956) (Fig. 2 D) Material. Nha Trang Bay: Diamond Bay, 1–2 m depth, coral rubble, 1 specimen. Description. Trunk pyriform or flask-shaped, 4 mm long, 2 mm wide in anterior trunk, about 2 mm in width in posterior trunk. Introvert about 2.5– 3 X shorter than trunk length, pale, without pigmented collar; hooks absent. Tentacular apparatus with four short stems; stems are equal in size, with bush-like tentacular branches; tentacles brown proximally, and in living specimens yellow distally. Discussion. T. cymodoceae, T. lageniformis and T. dehamata are the only three species in the subgenus Themiste (Lagenopsis) that have no introvert hooks. T. lageniformis is well distinguished from T. cymodoceae by having a purple pigmented introvert collar. T. dehamata is characterized by an elongated cylindrical trunk and tentacular stems of unequal length, while T. lageniformis and T. cymodoceae possess a pyriform trunk and tentacle stems of equal length. In contrast to the smaller bodied T. lageniformis, adult specimens of T. cymodoceae (previously known only from Australia) are much larger (trunk length commonly more than 40 mm). This is the first record of an adult specimen (with mature eggs) with trunk only 5 mm in length. It inhabits intertidal and shallow water areas, seagrass beds, and dead corals.Published as part of Adrianov, Andrey V. & Maiorova, Anastassya S., 2012, Peanut worms of the phylum Sipuncula from the Nha Trang Bay (South China Sea) with a key to species, pp. 41-58 in Zootaxa 3166 on page 46, DOI: 10.5281/zenodo.27977
- …
