8520561
Bounding the bandwidths for graphs
Let G;H be nite graphs with jV(H)j>jV(G)j. The bandwidth of G with respect to H is dened to be BH(G) = minmaxuv2E(G)dH((u);(v)), with the minimum taken over all injections from V(G )t oV(H), where dH(x;y) is the distance in H between two vertices x;y 2 V(H). This number is involved with the VLSI design and optimization, especially when the \host" graph H is a path Pn or a cycle Cn of length n = jV(G)j. In these two cases, BH(G) is known to be the ordinary bandwidth B(G) and the cyclic bandwidth Bc(G), respectively, and the corresponding decision problem is NP-complete. So estimations of B(G), Bc(G) and in general BH(G) are needed, especially in determining the bandwidths of some specic graphs. In this paper, we rst propose a systematic method for obtaining lower bounds for the bandwidth BH(G). By using this method, we then get a number of lower bounds for B(G) and Bc(G )i n terms of some distance- and degree-related parameters. c 2000 Elsevier Science B.V. All rights reserved.
34996713
Polynomial Time Solvability Of The Weighted Ring Arc-Loading Problem With Integer Splitting
In the Weighted Ring Arc-Loading Problem with Integer Splitting, we are given a set of communication requests each associated with a non-negative integer weight. The problem is to find a routing scheme such that the maximum load on arcs of the ring is minimized, subject to that the weight of each request may be split into two integral parts routed in two directions around the ring, where the load of an arc is the sum of parts routed through the arc. A pseudo-polynomial algorithm for this problem is implied by a result in [G. Wilfong and P. Winkler, Ring routing and wavelength translation, Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, San Fancisco, CA, 1998, 333-341]. By refining the rounding technique developed in the same paper, we prove that the problem can be solved in polynomial time.
38623555
Domination number and neighbourhood conditions
Abstract The domination number γ of a graph G is the minimum cardinality of a subset D of vertices of G such that each vertex outside D is adjacent to at least one vertex in D . For any subset A of the vertex set of G , let ∂ + ( A ) be the set of vertices not in A which are adjacent to at least one vertex in A . Let N (A) be the union of A and ∂ + ( A ), and d ( A ) be the sum of degrees of all the vertices of A . In this paper we prove the inequality 2q ⩽ (p−γ)(p−γ+2)−|∂ + (A)| (p−γ+1)+d( N (A)) , and characterize the extremal graphs for which the equality holds, where p and q are the numbers of vertices and edges of G , respectively. From this we then get an upper bound for γ which generalizes the known upper bound γ⩽p+1− 2q+1 . Let I ( A ) be the set of vertices adjacent to all vertices of A , and I (A) be the union of A and I ( A ). We prove that 2q ⩽ (p − γ − | I (A)| + 2)(p − γ + 4) + d( I (A)) − min {p − γ − | I (A)| + 2, |A|, |I(A)|, 3} , which implies an upper bound for γ as well.
32007375
Interpolation theorems for graphs, hypergraphs and matroids
Abstract Let P and Q be, respectively, hereditary and cohereditary properties defined on the subsets of a finite set S . We first prove that several functions related to P and Q interpolate over some families of subsets of S . By using this we then derive a number of interpolation results for graphs, hypergraphs and matroids.
20645165
Harper-type lower bounds and the bandwidths of the compositions of graphs
Abstract We give a general Harper-type lower bound for the bandwidth of a graph which is a common generalization of several known results. As applications we get a lower bound for the bandwidth of the composition of two graphs. By using this we determine the bandwidths of some composition graphs such as ( P r × P s )[ H ], ( P r × C s )[ H ] (2 r ≠ s ), ( C r × C s )[ H ] (6 ⩽ 2 r ⩽ s ), etc., for any graph H . Interestingly, the bandwidths of these graphs have nothing to do with the structure of H in general.
14537383
Constructing a Class of Symmetric Graphs
We find a natural construction of a large class of symmetric graphs from point- and block-transitive 1-designs. The graphs in this class can be characterized as G -symmetric graphs whose vertex sets admit a G -invariant partition B of block size at least 3 such that, for any two blocks B, C of B, either there is no edge between B and C, or there exists only one vertex in B not adjacent to any vertex inC . The special case where the quotient graph ?Bof ? relative to B is a complete graph occurs if and only if the 1-design needed in the construction is a G -doubly transitive and G -block-transitive 2-design, and in this case we give an explicit classification of ? when G is a doubly transitive projective group or an affine group containing the affine general group. Examples of such graphs include cross ratio graphs studied recently by Gardiner, Praeger and Zhou and some other graphs with vertices the (point, line)-flags of the projective or affine geometry.
8505547
Face recognition from video: a CONDENSATION approach
The aim of this work is to investigate how to exploit the temporal information in a video sequence for the task of face recognition. Following the approach in (Li and Chellappa, 2000), we propose a probabilistic model parameterized by a tracking state vector and a recognizing identity variable, simultaneously characterizing the kinematics and identity of humans. We then invoke a CONDENSATION (Isard and Blake, 1996) approach to provide a numerical solution to the model. Once the joint posterior distribution of the state vector and the identity variable is estimated, we marginalize it over the state vector to yield a robust estimate of the posterior distribution of the identity variable. Due to the propagation of identity and dynamics, a degeneracy in the posterior distribution of the identity variable is achieved to give improved recognition. This evolving behavior is characterized using changes in entropy. The effectiveness of this approach is illustrated using experimental results on low-resolution video data.
5971410
Time-space consistency in large-scale distributed virtual environments
Maintaining a consistent view of the simulated world among different simulation nodes is a fundamental problem in large-scale distributed virtual environments (DVEs). In this paper, we characterize this problem by quantifying the time-space inconsistency in a DVE. To this end, a metric is defined to measure the time-space inconsistency in a DVE. One major advantage of the metric is that it may be estimated based on some characteristic parameters of a DVE, such as clock asynchrony, message transmission delay, the accuracy of the dead reckoning algorithm, the kinetics of the moving entity, and human factors. Thus the metric can be used to evaluate the time-space consistency property of a DVE without the actual execution of the DVE application, which is especially useful in the design stage of a DVE. Our work also clearly shows how the characteristic parameters of a DVE are interrelated in deciding the time-space inconsistency, so that we may fine-tune the DVE to make it as consistent as possible. To verify the effectiveness of the metric, a Ping-Pong game is developed. Experimental results show that the metric is effective in evaluating the time-space consistency property of the game.
379157
From sample similarity to ensemble similarity: probabilistic distance measures in reproducing kernel Hilbert space
This paper addresses the problem of characterizing ensemble similarity from sample similarity in a principled manner. Using a reproducing kernel as a characterization of sample similarity, we suggest a probabilistic distance measure in the reproducing kernel Hilbert space (RKHS) as the ensemble similarity. Assuming normality in the RKHS, we derive analytic expressions for probabilistic distance measures that are commonly used in many applications, such as Chernoff distance (or the Bhattacharyya distance as its special case), Kullback-Leibler divergence, etc. Since the reproducing kernel implicitly embeds a nonlinear mapping, our approach presents a new way to study these distances whose feasibility and efficiency is demonstrated using experiments with synthetic and real examples. Further, we extend the ensemble similarity to the reproducing kernel for ensemble and study the ensemble similarity for more general data representations.
8965145
A robust algorithm for probabilistic human recognition from video
Human recognition from video requires solving the two tasks, recognition and tracking, simultaneously. This leads to a parameterized time series state space model, representing both motion and identity of the human. Sequential Monte Carlo (SMC) algorithms, like Condensation, can be developed to offer numerical solutions to this model. However in outdoor environments, the solution is more likely to diverge from the foreground, causing failures in both recognition and tracking. In this paper we propose an approach for tackling this problem by incorporating the constraint of temporal continuity in the observations. Experimental results demonstrate improvements over its Condensation counterpart.
135505
Image based regression using boosting method
We present a general algorithm of image based regression that is applicable to many vision problems. The proposed regressor that targets a multiple-output setting is learned using boosting method. We formulate a multiple-output regression problem in such a way that overfitting is decreased and an analytic solution is admitted. Because we represent the image via a set of highly redundant Haar-like features that can be evaluated very quickly and select relevant features through boosting to absorb the knowledge of the training data, during testing we require no storage of the training data and evaluate the regression function almost in no time. We also propose an efficient training algorithm that breaks the computational bottleneck in the greedy feature selection process. We validate the efficiency of the proposed regressor using three challenging tasks of age estimation, tumor detection, and endocardial wall localization and achieve the best performance with a dramatic speed, e.g., more than 1000 times faster than conventional data-driven techniques such as support vector regressor in the experiment of endocardial wall localization.