5800162
A sequential coloring algorithm for finite sets
Abstract Let X be a finite set and P a hereditary property associated with the subsets of X . A partition of X into n subsets each with property P is said to be a P-n -coloring of X . The minimum n such that a P-n -coloring of X exists is defined to be the P -chromatic number of X . In this paper we give a sequential coloring algorithm for P -coloring X . From the algorithm we then get a few upper bounds for the P -chromatic number. In particular, we generalize the Welsh-Powell upper bound for ordinary chromatic number to the case of P -chromatic number of any finite set X .
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.
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.
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.
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.
7512450
Simultaneous background and foreground modeling for tracking in surveillance video
We present a stochastic tracking algorithm for surveillance video where targets are dim and at low resolution. The algorithm builds motion models for both background and foreground by integrating motion and intensity information. Some other merits of the algorithm include adaptive selection of feature points for scene description and defining proper cost functions for displacement estimation. The experimental results show tracking robustness and precision in a challenging video sequences.
10450956
Pairwise Active Appearance Model and Its Application to Echocardiography Tracking
We propose a pairwise active appearance model (PAAM) to characterize statistical regularities in shape, appearance, and motion presented by a target that undergoes a series of motion phases, such as the left ventricle in echocardiography. The PAAM depicts the transition in motion phase through a Markov chain and the transition in both shape and appearance through a conditional Gaussian distribution. We learn from a database the joint Gaussian distribution of the shapes and appearances belonging to two consecutive motion phases (i.e., a pair of motion phases), from which we analytically compute the conditional Gaussian distribution. We utilize the PAAM in tracking the left ventricle contour in echocardiography and obtain improved tracking results in terms of localization accuracy when compared with expert-specified contours.
61202442
Probabilistic identity characterization for face recognition
We present a general framework for characterizing the object identity in a single image or a group of images with each image containing a transformed version of the object, with applications to face recognition. In terms of the transformation, the group is made of either many still images or frames of a video sequence. The object identity is either discrete- or continuous-valued. This probabilistic framework integrates all the evidence of the set and handles the localization problem, illumination and pose variations through subspace identity encoding. Issues and challenges arising in this framework are addressed and efficient computational schemes are presented. Good face recognition results using the PIE database are reported.
3804246
The missing links in the BGP-based AS connectivity maps
PAM2003 - The Passive and Active Measurement Workshop(http://www.pam2003.org), San Diego, USA, April 2003
12190727
Appearance Characterization of Linear Lambertian Objects, Generalized Photometric Stereo, and Illumination-Invariant Face Recognition
Traditional photometric stereo algorithms employ a Lambertian reflectance model with a varying albedo field and involve the appearance of only one object. In this paper, we generalize photometric stereo algorithms to handle all appearances of all objects in a class, in particular the human face class, by making use of the linear Lambertian property. A linear Lambertian object is one which is linearly spanned by a set of basis objects and has a Lambertian surface. The linear property leads to a rank constraint and, consequently, a factorization of an observation matrix that consists of exemplar images of different objects (e.g., faces of different subjects) under different, unknown illuminations. Integrability and symmetry constraints are used to fully recover the subspace bases using a novel linearized algorithm that takes the varying albedo field into account. The effectiveness of the linear Lambertian property is further investigated by using it for the problem of illumination-invariant face recognition using just one image. Attached shadows are incorporated in the model by a careful treatment of the inherent nonlinearity in Lambert's law. This enables us to extend our algorithm to perform face recognition in the presence of multiple illumination sources. Experimental results using standard data sets are presented