1708763
Multilevel Distance Labelings for Paths and Cycles
For a graph $G$, let $\diam(G)$ denote the diameter of $G$. For any two vertices $u$ and $v$ in $G$, let $d(u, v)$ denote the distance between $u$ and $v$. A multilevel distance labeling (or distance labeling) for $G$ is a function $f$ that assigns to each vertex of $G$ a nonnegative integer such that for any vertices $u$ and $v$, $|f(u)-f(v)| \geq \diam(G) - d_G(u, v) +1$. The span of $f$ is the largest number in $f(V)$. The radio number of $G$, denoted by $rn(G)$, is the minimum span of a distance labeling for $G$. In this paper, we completely determine the radio numbers for paths and cycles.
30709401
T-graphs and the channel assignment problem
Abstract T -colorings arose from the channel assignment problem in communications. Given a finite set T of non-negative integers, a T -coloring of a simple graph G is an assignment of a non-negative integer (channel) on every vertex of G , such that the difference of channels of two adjacent vertices does not fall in T . The T -span of G , denoted by sp T ( G ), is the minimum span among all possible T -colorings of G , where the span of a T -coloring is the difference between the largest and smallest channels used. This article applies T -graphs to explore the sets T that belong to these two collections: G = { T : greedy (or first-fit) algorithm provides T -spans for all complete graphs}, and E = { T : spt ( G ) = sp T ( K χ ( G ) ) for all graphs G , where χ is the chromatic number}. Given T , its T -graph has the vertex set of all non-negative integers so that two vertices are adjacent if their difference does not fall in T . We show that for any a ∈ Z + , the T -graph of aT is isomorphic to a disjoint product of a copies of the T -graph of T , where aT is the set obtained by multiplying every element of T by a . Based on this characterization, the following two results are attained. For any a ∈ Z + , T ∈ E if and only if aT ∈ E , and T ∈ G if and only if aT ∈ G . The second fact has been proven by Cozzens and Roberts (1991) from a different approach. We will completely solve the family of sets T = {0, s , s + 1,…, l } by providing a different proof of the fact T ∈ G (Tesman, 1989), and showing that T ∈ E if and only if l is a multiple of s . In addition, complete solutions for a more general family are obtained: for any a , s , l ∈ Z + with s ⩽ l , T = {0, as , a ( s + 1), a ( s + 2),…, al } ∪ A ∈ E , and T ϵ E if and only if l = ms for some m , where A ⊆{ as + 1, as + 2, …, al - 1}.
6586245
Reconstructing XML Subtrees from Relational Storage of XML documents
Numerous researchers have proposed to use relational databases to store and query XML documents. One important component of such systems is the XML subtree reconstruction, which reconstructs the subtrees rooted at the matching nodes of an XML query and returns them to the user as the query result. Existing reconstruction algorithms either do not support recursive XML view schema, or require expensive nested queries or joins of multiple relations. In this paper, we propose an efficient XML subtree reconstruction algorithm, Reconstruct, which overcomes these limitations and uses an efficient stack-based structural join algorithm to recover all the parent-child relationships between elements. One salient advantage of this algorithm is that it employs the inlining feature of the inlining-based storage of XML documents, which is known as one of the best relational XML storage schemes. Both our algorithmic analysis and experimental study show that Reconstruct is efficient and scalable.
12777678
Unsupervised Image Layout Extraction
We propose a novel unsupervised learning algorithm to extract the layout of an image by learning latent object-related aspects. Unlike traditional image segmentation algorithms that segment an image using feature similarity, our method is able to learn high-level object characteristics (aspects) from a large number of unlabeled images containing similar objects to facilitate image segmentation. Our method does not require human to annotate the training set and works without supervision. We use a graphical model to address the learning of aspects and layout extraction together. In particular, aspect-feature dependency from multiple images is learned via the expectation-maximization algorithm. We demonstrate that, by associating latent aspects to spatial structure, the proposed method achieves much better layout extraction results than using probabilistic latent semantic analysis.
15066544
Bidirectional interpretation of XQuery
XQuery is a powerful functional language to query XML data. This paper gives a bidirectional interpretation of XQuery to address the problem of updating XML data through materialized XQuery views. We first design an expressive bidirectional transformation language, and then translate XQuery expressions into the code of this language. As a result, an XQuery expression can execute in two directions: in the forward direction, it generates a materialized view from the source XML data; while in the backward direction, it updates the source data by putting back the updates on the view. we have implemented our approach and applied it to some XQuery use cases from a W3C draft, which confirms the practicability of this approach.
16699960
Circular chromatic number for iterated Mycielski graphs
Abstract For a graph G , let M( G ) denote the Mycielski graph of G . The t th iterated Mycielski graph of G , M t ( G ), is defined recursively by M 0 ( G )= G , and M t ( G )=M(M t −1 ( G )) for t ⩾1. Let χ c ( G ) denote the circular chromatic number of G . We prove two main results: (1) If G has a universal vertex x , then χ c (M( G ))= χ (M( G )) if χ c (G−x)>χ(G)− 1 2 and G is not a star, otherwise χ c ( M (G))=χ( M (G))− 1 2 ; and (2) χ c (M t ( K m ))= χ (M t ( K m )) if m ⩾2 t −1 +2 t −2 and t ⩾2.
17515399
Sizes of Graphs with Fixed Orders and Spans for Circular-Distance-Two Labelings
A k-circular-distance-two labeling (or k-c-labeling) of a simple graph G is a vertex-labeling, using the labels 0, 1, 2, · · · , k − 1, such that the “circular difference” (mod k) of the labels for adjacent vertices is at least two, and for vertices of distance-two apart is at least one. The σ-number, σ(G), of a graph G is the minimum k of a k-c-labeling of G. For any given positive integers n and k, let G(n, k) denote the set of graphs G on n vertices and σ(G) = k. We determine the maximum size (number of edges) and the minimum size of a graph G ∈ G(n, k). Furthermore, we prove that for any value p between the maximum and the minimum size, there exists a graph G ∈ G(n, k) of size p. These results are analogues of the ones by Georges and Mauro [4] on distance-two labelings.