Triangular line graphs and word sense disambiguation

Linguists often represent the relationships between words in a collection of text as an undirected graph G=(V,E), where V is the vocabulary and vertices are adjacent in G if and only if the words that they represent co-occur in a relevant pattern in the text. Ideally, the words with similar meanings give rise to the vertices of a component of the graph. However, many words have several distinct meanings, preventing components from characterizing distinct semantic fields. This paper examines how the structural properties of triangular line graphs motivate the use of a clustering coefficient on the triangular line graph, thereby helping to identify polysemous words. The triangular line graph of G, denoted by T(G), is the subgraph of the line graph of G where two vertices are adjacent if the corresponding edges in G belong to a K₃.     

Properly colored paths and cycles

In an edge-colored graph, let d^c(v) be the number of colors on the edges incident to v and let δ^c(G) be the minimum d^c(v) over all vertices v∈G. In this work, we consider sharp conditions on δ^c(G) which imply the existence of properly edge-colored paths and cycles, meaning no two consecutive edges have the same color.     

Covering with blocks in the non-symmetric case

Considering an infinite string of i.i.d. random letters drawn from a finite alphabet we define the cover timeW _n as the number of random letters needed until each pattern of lenghtn appears at least once as a substring. Sharp weak and a.s. limit results onW _n are known in the symmetric case, i.e., when the random letters are uniformly distributed over the alphabet. In this paper we determine the limit distribution ofW _n in the nonsymmetric case asn. Generalizations in terms of point processes are also proved.Dedicated to Endre Csáki on his 60th birthday.     

Polynomial algorithms for (integral) maximum two-flows in vertex edge-capacitated planar graphs

In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST₂-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST₂-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST₂-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one.     

ON THE TOTAL COLORING OF GRAPH G ∨H

ＯＮＴＨＥＴＯＴＡＬＣＯＬＯＲＩＮＧＯＦＧＲＡＰＨＧ∨Ｈ￥ＸｕＢａｏｇａｎｇ（许宝刚）（Ｍａｔｈ．ｏｆＤｅｐｔ．，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５０１００，Ｃｈｉｎａ．）Ａｂｓｔｒａｃｔ：Ｔｈｅｔｏｔａｌｃｈｒｏｍａｔｉｃｎｕｍｂ...     

Partial permutation decoding for the first-order Reed-Muller codes

Partial permutation decoding is shown to apply to the first-order Reed-Muller codes R(1,m), where m>4 by finding s-PD-sets for these codes for 2≤s≤4.