26190362
Enumerating branched orientable surface coverings over a non-orientable surface
The isomorphism classes of several types of graph coverings of a graph have been enumerated by many authors [M. Hofmeister, Graph covering projections arising from finite vector space over finite fields, Discrete Math. 143 (1995) 87-97; S. Hong, J.H. Kwak, J.Lee, Regular graph coverings whose covering transformation groups have the isomorphism extention property, Discrete Math. 148 (1996) 85-105; J.H. Kwak, J.H. Chun, J. Lee, Enumeration of regular graph coverings having finite abelian covering transformation groups, SIAM J. Discrete Math. 11 (1998) 273-285; J.H. Kwak, J. Lee, Isomorphism classes of graph bundles, Canad. J. Math. XLII (1990) 747-761; J.H. Kwak, J. Lee, Enumeration of connected graph coverings, J. Graph Theory 23 (1996) 105-109]. Recently, Kwak et al [Balanced regular coverings of a signed graph and regular branched orientable surface coverings over a non-orientable surface, Discrete Math. 275 (2004) 177-193] enumerated the isomorphism classes of balanced regular coverings of a signed graph, as a continuation of an enumeration work done by Archdeacon et al [Bipartite covering graphs, Discrete Math. 214 (2000) 51-63] the isomorphism classes of branched orientable regular surface coverings of a non-orientable surface having a finite abelian covering transformation group. In this paper, we enumerate the isomorphism classes of connected balanced (regular or irregular) coverings of a signed graph and those of unbranched orientable coverings of a non-orientable surface, as an answer of the question raised by Liskovets [Reductive enumeration under mutually orthogonal group actions, Acta-Appl. Math. 52 (1998) 91-120]. As a consequence of these two results, we also enumerate the isomorphism classes of branched orientable surface coverings of a non-orientable surface. Acta-Appl. Math. 52 (1998) 91-120]. As a consequence of these two results, we also enumerate the isomorphism classes of branched orientable surface coverings of a non-orientable surface.
29011378
The achromatic number of the union of cycles
The achromatic number of a graph G is the largest number of colors which can be assigned to the vertices of G so that adjacent vertices get different colors and each pair of distinct colors appears on the ends of some edge. We show that the achromatic number of the disjoint union of k cycles of length l1, l2 ...., lk is equal to the achromatic number of the cycle of length p = Σi=1k li for any k ≤ √p/2, and that the achromatic number of the disjoint union of k triangles (resp. quadrangles) is equal to the achromatic number of the cycle of length 3k (resp. 4k) for any positive integer k.
358063
Basic compiler algorithms for parallel programs
Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.
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.
7796564
CFLRU: a replacement algorithm for flash memory
In most operating systems which are customized for disk-based storage system, the replacement algorithm concerns only the number of memory hits. However, flash memory has different read and write cost in the aspects of time and energy so the replacement algorithm with flash memory should consider not only the hit count but also the replacement cost caused by selecting dirty victims. The replacement cost of dirty page is higher than that of clean page with regard to both access time and energy consumption. In this paper, we propose the Clean-First LRU (CFLRU) replacement algorithm that exploits the characteristics of flash memory. CFLRU splits the LRU list into the working region and the clean-first region and adopts a policy that evicts clean pages preferentially in the clean-first region until the number of page hits in the working region is preserved in a suitable level. Using the trace-driven simulation, the proposed algorithm reduces the average replacement cost by 28.4% in swap system and by 26.2% in buffer cache, compared with LRU algorithm. We also implement the CFLRU algorithm in the Linux kernel and present some optimization issues.
7999511
A proportional-share scheduler for multimedia applications
This paper presents a proportional-share CPU scheduler which can support multimedia applications in a general-purpose workstation environment. For this purpose, we have extended the stride scheduler which is designed originally for conventional tasks. New scheduling parameters are introduced to specify timing requirements of multimedia applications. Through the, use of the rate regulator, the accuracy error of the scheduling is reduced to O(1). Separate task groups are proposed to represent both relative shares and absolute shares. The proposed scheduler is evaluated using a simulation study. The results show that the proposed scheduler achieves improved accuracy and adaptability as well as fairness.
9196724
STRG-Index: spatio-temporal region graph indexing for large video databases
In this paper, we propose new graph-based data structure and indexing to organize and retrieve video data. Several researches have shown that a graph can be a better candidate for modeling semantically rich and complicated multimedia data. However, there are few methods that consider the temporal feature of video data, which is a distinguishable and representative characteristic when compared with other multimedia (i.e., images). In order to consider the temporal feature effectively and efficiently, we propose a new graph-based data structure called Spatio-Temporal Region Graph (STRG). Unlike existing graph-based data structures which provide only spatial features, the proposed STRG further provides temporal features, which represent temporal relationships among spatial objects. The STRG is decomposed into its subgraphs in which redundant subgraphs are eliminated to reduce the index size and search time, because the computational complexity of graph matching (subgraph isomorphism) is NP-complete. In addition, a new distance measure, called Extended Graph Edit Distance (EGED), is introduced in both non-metric and metric spaces for matching and indexing respectively. Based on STRG and EGED, we propose a new indexing method STRG-Index, which is faster and more accurate since it uses tree structure and clustering algorithm. We compare the STRG-Index with the M-tree, which is a popular tree-based indexing method for multimedia data. The STRG-Index outperforms the M-tree for various query loads in terms of cost and speed.