6994394
The Hamiltonian property of generalized de Bruijn digraphs
Abstract It has been shown that the generalized de Bruijn digraphs G B ( n , d ) and the Imase-Itoh digraphs G I ( n , d ) have Hamiltonian circuits of gcd ( n , d ) > 1. For gcd ( n , d ) = 1 the problem remains open except for d = 1 and 2. In this paper we give a unified proof for all d ≥ 3 that both G B ( n , d ) and G I ( n , d ) have Hamiltonian circuits.
2453836
On connectivity of consecutive-d digraphs
The concept of a consecutive-d digraph was proposed by Du, Hsu and Hwang as a generalization of de Bruijn digraphs, Kautz digraphs, and their generalizations given by Imase and Itoh and Reddy, Pradhan and Kuhl. In this paper, we determine the connectivity of consecutive-d digraphs and study how to modify consecutive-d digraphs to reach maximum connectivity. Our results will generalize and improve several existing results on the connectivity of de Bruijn digraphs, Kautz digraphs and Imase-Itoh digraphs.
30354625
A class of full Steiner minimal trees
A Steiner minimal tree for a given set of points in the plane is a tree which interconnects these points using lines of shortest possible total length. We construct an infinite class of trees which are the unique full Steiner minimal trees for their sets of endpoints (vertices of degree one).
14358235
New bounds on a hypercube coloring problem
In studying the scalability of optical networks, one problem which arises involves coloring the vertices of the n-cube with as few colors as possible such that any two vertices whose Hamming distance is at most k are colored differently. Determining the exact value of χ??(n), the minimum number of colors needed, appears to be a difficult problem. In this note, we improve the known lower and upper bounds of χ??(n) and indicate the connection of this coloring problem to linear codes.
36038781
A proof of the Gilbert-Pollak conjecture on the Steiner ratio
LetP be a set ofn points on the euclidean plane. LetLs(P) andLm(P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,Ls(P)≥(√3/2)Lm(P). We provide a proof for their conjecture in this paper.
43203779
The k-Steiner ratio in graphs
A Steiner minimum tree, SMT, is the shortest length tree in a metric space interconnecting a set of points, called the regular points, possibly using additional vertices. A k-size Steiner minimum tree, kSMT, is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-$lteiner ratio, pk, is the infimum of the ratios SMT/kSMT over all sets of regular points in all possible metric spaces, where the distances are given by a complete graph. Previously only p2 and p3 in graphs had been known exactly, and some bounds where know for the others. In this paper we determine pk exactly for all k.
17041567
On-line scheduling of small open shops
We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.
11088545
Supporting Random Access on Real-Time Retrieval of Digital Continuous Media
In addition to the large data size requirement and real-time constraint in continuous media, future video applications such as video editing demand a random access capability at the video-frame level. This paper introduces our study on effective buffering control for the real-time retrieval of jitter-free digital video medium. We adopt a video-frame level approach to maintaining the flexibility on placement and analysing the efficiency of the buffering schemes. An integrated solution which offers efficient buffering schemes and flexible storage placement to support random access is our goal. We present two buffering schemes: the two-buffer scheme and the k-buffer compensation scheme. The two-buffer scheme requires that all the frames in a block are stored consecutively, while providing random access between blocks. However, this intuitive buffering scheme potentially requires a large block size and buffer space. The k-buffer compensation scheme is proposed to resolve this large buffer space requirement, by using more than two buffers and requiring a minimal number of blocks randomly placed in each cylinder. This scheme differs from the contiguous placement scheme because individual blocks can be stored anywhere in each cylinder. Compared to the two-buffer scheme, the k-buffer compensation scheme requires less buffer space, has higher disk utilization and finer granularity on disk data transfer. The placement requirements are more flexible and implementable than the contiguous and storage pattern placement schemes. Experimental measurement results reveal the significant improvements on the buffer-size reduction and placement flexibility by using the k-buffer compensation scheme. Extensions of the k-buffer compensation scheme to support multiple streams are also addressed.
16471624
Preemptive on-line scheduling for two uniform processors
This paper considers the problem of preemptive on-line scheduling for two uniform processors in which one of the processors has speed 1 and the other has speed s>=1. The objective is to minimize the makespan. A best possible algorithm with competitive ratio of (1+s)^2/(1+s+s^2) is proposed for this problem.
35793386
An improved algorithm for decomposing arc flows into multipath flows
We consider a multipath maximum flow problem introduced by Kishimoto (Networks 27(4)(1996)279-291). The focus is on efficient transformation from arc flows into multipath flows, where a multipath flow is a nonnegative combination of multipaths. A new algorithm that is more efficient than existing ones is proposed for the transformation.
2477251
PCR-assist CBR for delivering pre-recorded MPEG-2 transport streams
Transmitting compressed variable bit-rate (VBR) video with a traditional constant bit-rate (CBR) service for continuous playback requires a large buffer on the viewer's side. In this paper, we study a new CBR transmission scheme which employs the program clock references (PCR) that are embedded in the MPEG-2 transport streams to reduce the buffer requirement. The scheme is called "PCR-assist CBR" (PCBR). The PCBR scheme uses PCRs to examine its transmission regularly. It holds up the transmission if it is ahead of schedule. Based on experimental results with video traces, the PCBR scheme reduces the buffer requirement at the cost of a higher transmission rate.