TITLE

# Minimum-weight perfect matching for nonintrinsic distances on the line

AUTHOR(S)
Delon, J.; Salomon, J.; Sobolevski, A.
PUB. DATE
March 2012
SOURCE
Journal of Mathematical Sciences;Mar2012, Vol. 181 Issue 6, p782
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
We consider a minimum-weight perfect matching problem on the line and establish a 'bottom-up' recursion relation for weights of partial minimum-weight matchings. Bibliography: 11 titles.
ACCESSION #
73557679

## Related Articles

• UNDERLYING GRAPHS OF 3-QUASI-TRANSITIVE DIGRAPHS AND 3-TRANSITIVE DIGRAPHS RUIXIA WANG, SHIYING WANG. RUIXIA WANG; SHIYING WANG // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p429

A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). CÃ©sar HernÃ¡ndez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation....

• 4-TRANSITIVE DIGRAPHS I: THE STRUCTURE OF STRONG 4-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p247

Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v, w âˆˆ V (D), (u, v), (v, w) âˆˆ A(D) implies that (u, w) âˆˆ A(D). This concept can be generalized as follows: A digraph...

• Characterization of Line Sidigraphs. Sampathkumar, E.; Subramanya, M. S.; Reddy, P. Siva Kota // Southeast Asian Bulletin of Mathematics;2011, Vol. 35 Issue 2, p297

A sigraph (sidigraph) is an ordered pair S = (G; Ïƒ) (S = (D; Ïƒ)), where G = (V, E) (D = (V, A) is a graph (digraph) called the underlying graph (underlying digraph) of S and Ïƒ : E â†’ {+, -} (&sigma: A â†’ {+, -}) is a function. The line sigraph (line sidigraph) of a sigraph...

• An Algorithm to Detect Cycle in an Undirected Graph. Kumar, Anand; Jani, N. N. // International Journal of Computational Intelligence Research;2010, Vol. 6 Issue 2, p305

This paper presents a novel algorithm to detect cycles in a graph. The graph may be of any type. Cycles are available in a graph and in much real life application; it is required to know the existence of cycles in a graph. This algorithm is developed in the context of network design problem but...

• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs. Liang, Hao; Xu, Jun // Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53

For a simple digraph G, let Î²( G) be the size of the smallest subset X âŠ† E( G) such that Gâˆ’X has no directed cycles, and let Î³( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This...

• Products and Eccentric Diagraphs. Medha Itagi Huilgol; S. Syed Asif Ulla // British Journal of Mathematics & Computer Science;2014, Vol. 4 Issue 6, p805

The eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a graph(digraph) G is the digraph that has the same vertex as G and an arc from u...

• A Contribution to the Second Neighborhood Problem. Ghazal, Salman // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1365

Seymour's Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We...

• SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651

A digraph D is k-transitive if the existence of a directed path (v0, v1, ..., vk), of length k implies that (v0, vk) âˆˆ & A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an...

• Uniform Coverings of 2-paths in the Complete Bipartite Directed Graph. Midori Kobayashi; Keiko Kotani; Nobuaki Mutoh; Gisaku Nakamura // AIP Conference Proceedings;2015, Vol. 1648 Issue 1, p1

Let G be a directed graph and H be a subgraph of G. A D(G, H, Î») design is a multiset D of subgraphs of G each isomorphic to H so that every directed 2-path in G lies in exactly Î» subgraphs in D. In this talk, we show that there exists a D(Kn,n*, C2n, 1) design for every n â‰¥ 2, where...

Share