A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each ...
详细信息
A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)| >= min{5, triangle + 1} for each vertex v and |L(e)| >= max{5, d(v) + 1, d(w) + 1} for each edge e = vw, where triangle is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with triangle + 1 colors if triangle >= 4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition. (C) 2004 Elsevier B. V. All rights reserved.
This paper presents a novel two-pass algorithm constituted by linear Hashtable Motion Estimation algorithm (LHMEA) and Hexagonal Search (HEXBS). compensation. for block base motion On the basis of research from previo...
详细信息
ISBN:
(纸本)0889865280
This paper presents a novel two-pass algorithm constituted by linear Hashtable Motion Estimation algorithm (LHMEA) and Hexagonal Search (HEXBS). compensation. for block base motion On the basis of research from previous algorithms, especially an on-the-edge motion estimation algorithm called hexagonal search (HEXBS), we propose the LHMEA and the Two-Pass algorithm (TPA). We introduce hashtable into video compression. In this paper we employ LHMEA for the first-pass search in all the Macroblocks (MB) in the picture. Motion Vectors (MV) are then generated from the first-pass and are used as predictors for second-pass HEXBS motion estimation, which only searches a small number of MBs. The evaluation of the algorithm considers the three important metrics being time, compression rate and PSNR. The performance of the algorithm is evaluated by using standard video sequences and the results are compared to current algorithms. Experimental results show that the proposed algorithm can offer the same compression rate as the Full Search. LHMEA with TPA has significant improvement on HEXBS and shows a direction for improving other fast motion estimation algorithms, for example Diamond Search.
Binary comparison operators form the basis of consumer set theory. If humans could only perform binary comparisons, the most efficient procedure a human might employ to make a complete preference ordering of n items w...
详细信息
Binary comparison operators form the basis of consumer set theory. If humans could only perform binary comparisons, the most efficient procedure a human might employ to make a complete preference ordering of n items would be a n log(2)n algorithm. But, if humans are capable of assigning each item an ordinal utility value, they are capable of implementing a more efficient linear algorithm. In this paper, we consider six incentive systems for ordering three different sets of objects: pens, notebooks, and Hot Wheels. All experimental evidence indicates that humans are capable of implementing a linear algorithm, for small sets. (C) 2003 Elsevier Science B.V. All rights reserved.
This paper introduces a simple method for obtaining the pure 3-D translational motion parameter (without rotation) and the translation parameter with a known rotation of a camera. Once the translation vector is availa...
详细信息
This paper introduces a simple method for obtaining the pure 3-D translational motion parameter (without rotation) and the translation parameter with a known rotation of a camera. Once the translation vector is available, the 3-D structure of an object can also be obtained. The minimum number of matching points in the two images can be as few as two, and the equations to be solved are linear. Synthetic and real image tests has been performed, and good results have been obtained.
Trilinear relationships among the image point coordinates obtained by perspective projection of several feature points over three views have been investigated, and it has been shown that seven point correspondences ar...
详细信息
Trilinear relationships among the image point coordinates obtained by perspective projection of several feature points over three views have been investigated, and it has been shown that seven point correspondences are sufficient to determine the coefficients involved. We show that analogous trilinear relationships exist for the weak perspective and paraperspective projections, and that only four point correspondences are necessary for the determination of the coefficients. When the trilinear relationships are known, the position of the image of a point in one camera system can be determined from its image in the two other camera systems through linear equations. (C) 2000 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
In this paper we address the problem of planning the capacity of the local rings in synchronous optical networks (SONET). We present efficient lower and upper bound procedures and a branch and bound algorithm which is...
详细信息
In this paper we address the problem of planning the capacity of the local rings in synchronous optical networks (SONET). We present efficient lower and upper bound procedures and a branch and bound algorithm which is able to find the exact solution of large instances, employing short computing times. (C) 1999 Elsevier Science B.V. All rights reserved.
A discrete optimization problem of assigning linearly ordered character-states to the hypothetical ancestors of an evolutionary tree under the principle of maximum parsimony has been discussed. Under the transformatio...
详细信息
A discrete optimization problem of assigning linearly ordered character-states to the hypothetical ancestors of an evolutionary tree under the principle of maximum parsimony has been discussed. Under the transformation relation of linearly ordered character-states, Farris (1970) and Swofford and Maddison (1987) have dealt with the problem on completely bifurcating phylogenetic trees and presented a solution. Hanazawa et al. (1995) have mathematically formulated the problem with its generalization to any tree and called it the MPR (most-parsimonious reconstruction) problem. Then they have presented clear algorithms for the MPR problem and the related problems. We present a more efficient algorithm for one of the problems, the problem of obtaining the MPR sets. The complexity of the previous algorithm for this problem is O(n(2)) for the number n of nodes in a given tree, but that of the new algorithm is O(n).
This paper is concerned with the problem of capturing meaningful and useful visibility information inside a simple polygon given only an inaccurate representation of the vertices of the polygon. We introduce a. notion...
详细信息
This paper is concerned with the problem of capturing meaningful and useful visibility information inside a simple polygon given only an inaccurate representation of the vertices of the polygon. We introduce a. notion of a visibility skeleton of an inaccurate representation of a simple polygon. We show that in most cases the visibility skeleton of a representation can be computed efficiently;furthermore, the visibility skeleton can be used to plan a collision-free path inside the polygon whose length approximates the length of a shortest such path to within a constant factor (independent of the number of vertices in the polygon).
We propose a new algorithm to simultaneously recover the motion and 3D shape of moving objects from feature points of the moving objects in an orthographic projection. Given the assumption that the moving object is a ...
详细信息
We propose a new algorithm to simultaneously recover the motion and 3D shape of moving objects from feature points of the moving objects in an orthographic projection. Given the assumption that the moving object is a rigid body, the newly proposed algorithm uses times series correspondence of feature point coordinates in the orthographic projections and is based on the correspondence of 4 feature points at 3 points in time where the existence of a solution has been demonstrated. The merit of this algorithm is that it is a linear algorithm for recovery that uses only observed data, has the condition of unique recovery solution in principle, and can be applied in a unified manner in the case of a unique solution. In this method, after the possibility of recovery is determined by calculating the rank of the matrix, the recovery solution can quickly be found in a unified manner through a linear computation including matrix inversion computations. This theory solves the usual problems in the linear recovery theory in the recovery of moving objects from the point correspondence in orthographic projections and is segmented in theory. We verified the validity of this algorithm using simulation data generated by a computer, and after obtaining corresponding points, verified that real-time processing with an average recovery time of 4.6 ms is possible even for a personal computer CPU processing. In addition, the effectiveness of this algorithm was confirmed by using the real image of a moving object.
In this paper, we are concerned with a problem of robust control-oriented system identification in the time domain. Based on the well-known Schur-Takagi-AAK Theorem, we propose a linear algorithm to obtain the nominal...
详细信息
In this paper, we are concerned with a problem of robust control-oriented system identification in the time domain. Based on the well-known Schur-Takagi-AAK Theorem, we propose a linear algorithm to obtain the nominal model of the plant to be identified and the minimal bound of the uncertainty of the nominal model error which is measured by H(infinity)-norm. It is also shown that, in the model set defined by the nominal model and the uncertainty bound, there exists at least one model which matches the prescribed input-output data given in the time domain.
暂无评论