3161617
Isomorphism Classes of Concrete Graph Coverings
Hofmeister introduced the notion of a concrete (resp., concrete regular) covering of a graph G and gave formulas for enumerating the isomorphism classes of concrete (resp., concrete regular) coverings of G [Ars Combin., 32 (1991), pp. 121--127; SIAM J. Discrete Math., 8 (1995), pp. 51--61]. In this paper, we show that the number of the isomorphism classes of n-fold concrete (resp., concrete regular) coverings of G is equal to that of the isomorphism classes of n-fold (resp., regular) coverings of a new graph, the join $G+\infty$ of G and an extra vertex $\infty$. As a consequence, we can enumerate the isomorphism classes of concrete (resp., concrete regular) coverings of a graph by using known formulas for enumerating the isomorphism classes of coverings (resp., regular coverings) of a graph.
623251
Isomorphism classes of bipartite cycle permutation graphs
207081381
Enumeration of Regular Graph Coverings Having Finite Abelian Covering Transformation Groups
Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors. An enumeration of the isomorphism classes of n-fold coverings of a graph G was done by Kwak and Lee [Canad. J. Math., XLII (1990), pp. 747--761] and independently by Hofmeister [Discrete Math., 98 (1991), pp. 437--444]. An enumeration of the isomorphism classes of connected n-fold coverings of a graph G was recently done by Kwak and Lee [J. Graph Theory, 23 (1996), pp. 105--109]. But the enumeration of the isomorphism classes of regular coverings of a graph G has been done for only a few cases. In fact, the isomorphism classes of ${\cal A}$-coverings of G were enumerated when ${\cal A}$ is the cyclic group $\BZ_n$, the dihedral group $\BD_n$ (n: odd), and the direct sum of $m$ copies of $\BZ_p$. (See [Discrete Math., 143 (1995), pp. 87--97], [J. Graph Theory, 15 (1993), pp. 621--627], and [Discrete Math., 148 (1996), pp. 85--105]). 
In this paper, we discuss a method to enumerate the isomorphism classes of connected ${\cal A}$-coverings of a graph G for any finite group ${\cal A}$ and derive some formulas for enumerating the isomorphism classes of regular n-fold coverings for any natural number n. In particular, we calculate the number of the isomorphism classes of ${\cal A}$-coverings of G when ${\cal A}$ is a finite abelian group or the dihedral group $\BD_n$. Our method gives partial answers to the open problems 1 and 2 in [Discrete Math., 148 (1996), pp. 85--105] and also gives a formula to calculate the number of the subgroups of a given index of any finitely generated free abelian group.
16002222
Isomorphism classes of cycle permutation graphs
Abstract In this paper, we construct a cycle permutation graph as a covering graph over the dumbbell graph, and give a new characterization of when two given cycle permutation graphs are isomorphic by a positive or a negative natural isomorphism. Also, we count the isomorphism classes of cycle permutation graphs up to positive natural isomorphism, and find the number of distinct cycle permutation graphs isomorphic to a given cycle permutation graph by a positive/negative natural isomorphism. As a consequence, we obtain a formula for finding the number of double cosets of the dihedral group in the symmetric group.
40285902
Isoperimetric numbers and bisection widths of double coverings of a complete graph
6516775
Distributions of regular branched surface coverings
In a study of surface branched coverings, one can ask naturally: In how many different ways can a given surface be a branched covering of another given surface? This problem was studied by many authors in Quart. J. Math. Oxford Ser. 2 46 (1995) 485, Math. Scand. 84 (1999) 23, Discrete Math. 156 (1996) 141, Discrete Math. 183 (1998) 193, Discrete Math. (in press), European J. Combin. 22 (2001) 1125, Sibirsk. Mat. Zh. 25 (1984) 606 etc. In this paper, as a complete answer to the question for regular coverings, we determine the distribution of the regular branched coverings of any nonorientable surface S when the covering transformation group and a set of branch points are freely assigned.
14238943
Secure query processing against encrypted XML data using Query-Aware Decryption
Dissemination of XML data on the internet could breach the privacy of data providers unless access to the disseminated XML data is carefully controlled. Recently, the methods using encryption have been proposed for such access control. However, in these methods, the performance of processing queries has not been addressed. A query processor cannot identify the contents of encrypted XML data unless the data are decrypted. This limitation incurs overhead of decrypting the parts of the XML data that would not contribute to the query result. In this paper, we propose the notion of Query-Aware Decryption for efficient processing of queries against encrypted XML data. Query-Aware Decryption allows us to decrypt only those parts that would contribute to the query result. For this purpose, we disseminate an encrypted XML index along with the encrypted XML data. This index, when decrypted, informs us where the query results are located in the encrypted XML data, thus preventing unnecessary decryption for other parts of the data. Since the size of this index is much smaller than that of the encrypted XML data, the cost of decrypting this index is negligible compared with that for unnecessary decryption of the data itself. The experimental results show that our method improves the performance of query processing by up to six times compared with those of existing methods. Finally, we formally prove that dissemination of the encrypted XML index does not compromise security.
3952650
Haptic pen: a tactile feedback stylus for touch screens
In this paper we present a system for providing tactile feedback for stylus-based touch-screen displays. The Haptic Pen is a simple low-cost device that provides individualized tactile feedback for multiple simultaneous users and can operate on large touch screens as well as ordinary surfaces. A pressure-sensitive stylus is combined with a small solenoid to generate a wide range of tactile sensations. The physical sensations generated by the Haptic pen can be used to enhance our existing interaction with graphical user interfaces as well as to help make modern computing systems more accessible to those with visual or motor impairments.
9094168
Microscopic examination of TCP flows over transatlantic links
Much of the recent research and development in the area of high-speed TCP is focused on the steady state behavior of TCP flows. However, our experience with the first research only transatlantic 2.5 Gbps Lambda link clearly demonstrates the need to focus on the initial stages of TCP. The work we present here examines the behavior of TCP flows at microscopic level over high-bandwidth long delay networks. This examination has led us to study the influence of the minute properties of the underlying network on bursty protocols such as TCP at these very high speeds combined with high latency. In this paper we briefly describe the requirements for such an extreme network environment to support high-speed TCP flows. We also present results collected using transatlantic links at iGrid2002 where we tuned various host parameters and used modified TCP stacks.
6995202
Odysseus: a high-performance ORDBMS tightly-coupled with IR features
We propose the notion of tight-coupling [K. Whang et al., (1999)] to add new data types into the DBMS engine. In this paper, we introduce the Odysseus ORDBMS and present its tightly-coupled IR features (US patented). We demonstrate a Web search engine capable of managing 20 million Web pages in a non-parallel configuration using Odysseus.
15406780
Scenario based dynamic video abstractions using graph matching
In this paper, we present scenario based dynamic video abstractions using graph matching. Our approach has two main components: multi-level scenario generations and dynamic video abstractions. Multi-level scenarios are generated by a graph-based video segmentation and a hierarchy of the segments. Dynamic video abstractions are accomplished by accessing the generated hierarchy level by level. The first step in the proposed approach is to segment a video into shots using Region Adjacency Graph (RAG). A RAG expresses spatial relationships among segmented regions of a frame. To measure the similarity between two consecutive RAGs, we propose a new similarity measure, called Graph Similarity Measure (GSM). Next, we construct a tree structure called scene tree based on the correlation between the detected shots. The correlation is computed by the GSM since it considers the relations between the detected shots properly. Multi-level scenarios which provide various levels of video abstractions are generated using the constructed scene tree. We provide two types of abstraction using multi-level scenarios: multi-level highlights and multi-length summarizations. Multi-level highlights are made by entire shots in each scenario level. To summarize a video in various lengths, we select key frames by considering temporal relationships among RAGs computed by the GSM. We have developed a system, called Automatic Video Analysis System (AVAS), by integrating the proposed techniques to show their effectiveness. The experimental results show that the proposed techniques are promising.