24107558
Lower Bounds on the Minus Domination and k-Subdomination Numbers
A three-valued function f defined on the vertex set of a graph G = (V,E), f : V → {-1, 0, 1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is f(V) = Σv∈V f(v). The minus domination number of a graph G, denoted by γ-(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by J. Dunbar etc. (Discrete Math. 199(1999) 35-47), and we give a lower bound on γks(G) of a graph G.
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.
36724744
A decomposition theorem on Euclidean Steiner minimal trees
The Euclidean Steiner minimal tree problem is known to be an NP-complete problem and current alogorithms cannot solve problems with more than 30 points. Thus decomposition theorems can be very helpful in extending the boundary of workable problems. There have been only two known decomposition theorems in the literature. This paper provides a 50% increase in the reservoir of decomposition theorems.
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.
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.
206027538
A coloring problem on the n-cube
Abstract In this paper, we consider a coloring problem on the n-cube that arises in the study of scalability of optical networks. Let χ k (n) be the minimum number of colors needed to color the vertices of the n-cube so that every two vertices with Hamming distance ⩽k have different colors. We show that for k=3, 2n⩽χ 3 (n)⩽2 ⌈ log 2 n⌉+1 . We also provide upper and lower bounds on χ k (n) for general k.
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.
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.
9933311
The k-Steiner Ratio in the Rectilinear Plane
A Steiner minimum tree (SMT) in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points, possibly using additional vertices. Ak-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at mostkleaves. Thek-Steiner ratio in the rectilinear plane, ?k, is the infimum of the ratios SMT/kSMT over all finite sets of regular points. Thek-Steiner ratio is used to determine the performance ratio of several recent polynomial-time approximations for Steiner minimum trees. Previously it was known that in the rectilinear plane, ?2=2/3, ?3=4/5, and (2k?2)/(2k?1)??k(L1)?(2k?1)/(2k) fork?4. In 1991, P. Berman and V. Ramaiyer conjectured that in fact ?k=(2k?1)/(2k) fork?4. In this paper we prove their conjecture.
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.
18860643
The multiroute maximum flow problem revisited
We are given a directed network G = (V, A, u) with vertex setV , arc setA, a source vertexs ∈ V , a destination vertex t ∈ V , a finite capacity vector u = {uij}ij∈A, and a positive integerm ∈ Z+. The multiroute maximum flow problem ( m-MFP) generalizes the ordinary maximum flow problem by seeking a maximum flow from s to t subject to not only the regular flow conservation constraints at the vertices (except s andt) and the flow capacity constraints at the arcs, but also the extra constraints that any flow must be routed alon g m arc-disjoints-t paths. In this paper, we devise two new combinatorial algorithms for m-MFP. One is based on Newton’s method and another is based on augmenting-path technique. We also show how the Newton-based algorithm unifies two existing algorithms, and how the augmen ting-path algorithm is strongly polynomial for case m = 2.