Search

This paper examines whether clique-structure in cognitive data (i.e. recall of who one talks to) may be used as a proxy for clique-structure in behavioral data (i.e. who one actually talks to). The answer to this question is crucial to much of sociometric and social net-theoretic studies of social structure. We analysed the clique structures of the communication patterns of four naturally occurring groups of sizes 34 to 58, whose actual communications could easily be monitored, together with the groups' perceptions of their communications. The groups used were: radio hams, a college fraternity, a group of office workers, and an academic department. The analysis used clique-finding, block-modelling, and factor-analytic techniques, all employed in such a way as to maximize the accuracy of the cognitive data. After defining a way to compare clique structures between behavioral and cognitive data, we found that there was no useful relationship between the two, and furthermore there was no significant difference in performance between any of the structure-finding algorithms. We conclude that cognitive data may not be used for drawing any conclusions about behavioral social structure. [ABSTRACT FROM AUTHOR]

Everett (1982) has proposed a graph theoretic blocking procedure for social networks. In this paper we give a comprehensive description of the implementation of this procedure with special reference to a FORTRAN program contained in the Appendix. [ABSTRACT FROM AUTHOR]

In this paper we show how the algorithm EBLOC can be extended to deal with valued data directly. The technique is then applied to Sampson's (1969) monastery data and comparisons are made with the original EBLOC algorithm. [ABSTRACT FROM AUTHOR]

This article announces that the first Conference of the International Federation of Classification Societies will be held on June 29-July 1, 1987. The Conference is devoted to the presentation of theoretical and applied papers on Classification and related methods of data analysis in the broad sense. This includes mathematical and statistical as well as practical investigations, survey papers on the state of the art, real case studies, papers on numerical and algorithmic aspects, applications in special fields of knowledge, and the interface between classification and information sciences.

The orbits or a graph, digraph or network provide an effective definition for role equivalence since they are a natural generalization of the principle of substitutability of structural equivalence. Calculation of the orbits is a computationally difficult task but in this paper we present a fast and efficient algorithm which finds the orbits of a large class of graphs. In addition, we suggest a simple measure of role similarity based upon the constructions contained within the algorithm. This makes it possible to perform a role analysis when only a limited number of automorphisms exist. [ABSTRACT FROM AUTHOR]

The study of citation networks for both articles and journals is routine. In general, these analyses proceed by considering the similarity of articles or journals and submitting the set of similarity measures to some clustering or scaling procedure. Two common methods are found in bibliometric coupling, where two citing articles are similar to the extent they cite the same literature, and co-citation analysis where cited articles are similar to the extent they are cited by the same citing articles. Methods based on structural and regular equivalence also seek to partition the article based on their positional location. Such methods have in common focus on the articles and partitions of them. We propose a quite different approach where the connective threads through a network are preserved and the focus is on the links in the network rather than on the nodes. Variants of the depth first search algorithm are used to detect and represent the mainstream of the literature of a clearly delineated area of scientific research. The specific citation network is one that consists of ties among the key events and papers that lead to the discovery and modeling of DNA together with the final experimental confirmation of its representation. [ABSTRACT FROM AUTHOR]

In this paper, we explore the structure of the set of all regular equivalences (White and Reitz 1983), proving that it forms a lattice, and suggest a general approach to computing certain elements of the lattice. The resulting algorithm represents a useful complement to the White and Reitz algorithm, which can only find the maximal regular equivalence of a graph. Using this algorithm, it is possible to compute several well-known equivalences, such as structural equivalence. (Lorrain and White 1971), automorphic equivalence (Everett and Borgatti 1988), and Winship-Pattison equivalence (Winship and Mandel 1983). In addition, any number of other useful equivalences may be generated, providing suitable mathematical descriptions of them are available. [ABSTRACT FROM AUTHOR]

An individual's "status" is the position in a social network, which is usefuly modeled by the mathematical properties of directed graphs. Katz (1953) argued that an index of status based on "who chooses whom" should also include information on the status of the choosers. This recursive concept os status was adapted by Sade (1972), who used the sum of inward directed paths as a measure of centrality to distinguish the position of individual monkeys in a grooming network. Sade et al. (1988) used the same measure to describe the progression through time of the statuses of a set of male monkeys. These studies were limited by the, perceived computational difficulties in finding paths longer than 3-paths. Although ad hoc formulae for up to 6-paths were available from Ross and Harary (1952) and a general algorithm was known from Parthasarathy (1964) the methods were cumbersome and impractical to apply to large networks. The present paper makes use of a simple counting algorithm to find the n-paths in a binary matrix. The characteristics of centrality statuses in the grooming network are then describing using paths of up to maximum length, thus avoiding the limitations of the earlier studies. [ABSTRACT FROM AUTHOR]

This paper considers the use of the Bond Energy approach of McCormick, Schweitzer, and White as an alternative to CONCOR and other methods for producing blockmodel, and to Baker's approach to three-way blockmodels. Results of analyses using artificial data and the Roethlis- berger-Dickson Bank Wiring Room data are presented, where algorithms alternative to the one of McCormick et at (including versions of simulated annealing) are considered. [ABSTRACT FROM AUTHOR]

Search algorithms that have been developed in the discipline computer science can be applied to the analysis of social networks. These algorithms generally provide two capabilities useful for network analysis: very efficient means of "visiting' every node in a network, and a method of generating all possible paths through a network. The basic search algorithm is called the depth first search algorithm. To implement this algorithm efficiently requires the use of data structures not commonly used in social network analysis at the present time, the singly linked list, and the doubly linked list (sparse matrix). This paper describes how to use depth first search based algorithms and linked list data structures for analyzing the connectivity of social networks. We also propose new measures of connectivity, and use these measures to identify structural properties of networks that capture the connectivity of the network. [ABSTRACT FROM AUTHOR]

Network analysis has become a popular method for identifying the communication structure in a system where positional and relational aspects are important. In this paper, a maximum likelihood based methodology is presented that allows for the analysis of binary sociometric data. This methodology provides a network representation via estimated path-length or additive trees that indicate the distance between all pairs of members. The methodology is distinguished from traditional hierarchical clustering based procedures by its direct consideration of the asymmetry in a typical communication process, the simultaneous representation of structural characteristics (e.g., clique membership, clique cohesiveness), and the identification of the specialized communication roles of each member (e.g., opinion leader, liaison). A penalty function algorithm is developed and its performance is investigated via a Monte Carlo analysis with synthetic data. An application examining information flows among managers is presented. Finally, directions for future research are suggested. [ABSTRACT FROM AUTHOR]

The literature devoted to the construction of stochastic blockmodels is relatively rare compared to that of the deterministic variety. En this paper, a general definition of a stochastic blockmodel is given and a number of techniques for building such blockmodels are presented. In the statistical approach, the likelihood ratio statistic provides a natural index to evaluate the fit of the model to the data. The model itself consists of a set of actors partitioned into positions with respect to a definition of equivalence, and a representation based on estimated probabilities. The specific statistical model that is used to illustrate the techniques is P1, which was first introduced as a method for stochastic blockmodeling by Fienberg and Wasserman (1981), and developed by Holland et at. (1983) and Wasserman and Anderson (1987). [ABSTRACT FROM AUTHOR]

In this paper we present two algorithms for computing the extent of regular equivalence among pairs of nodes in a network. The first algorithm, REGE, is well known, but has not previously been described in the literature. The second algorithm, CATREGE, is new. Whereas REGE is applicable to quantitative data, CATREGE is used for categorical data. For binary data, either algorithm may be used, though the CATREGE algorithm is significantly faster and its output similarity coefficients have better metric properties. The CATREGE algorithm is also useful pedagogically, because it is easier to grasp. [ABSTRACT FROM AUTHOR]

This paper explores the application of two contemporary computational methods to the development of sociological theory. Specifically, we combine the methods of object-orientation with discrete event simulation. This approach has several advantages for constructing and evaluating dynamic social theories. In object-oriented program design, objects combine and integrate the traditional concepts of data structures and algorithms, the building blocks of structured programming. Algorithms associated with objects are called methods or member functions. Constructing social actors as objects involves defining both their data attributes and the methods associated with these attributes. We also treat a social network as a computational object. It has data types of nodes and ties. As an object, the network must also have methods that add and delete nodes and ties. Once a network exists, we can create other data types and methods that describe and analyze the network. For example, networks have in-degree and out-degree vectors, and measures of hierarchy. In principle, we can create attributes of networks for all of the structural measures we use to describe networks. We use actor and network objects in a discrete event simulation of a process of formation of dominance structures, exploring several dynamic variations of the underlying theoretical model. [ABSTRACT FROM AUTHOR]

Byline: Wu-Ji Li (a), J. MacGregor Smith (b) Abstract: Facility layout and location problems with stochastic congestion in the traffic circulation system have been studied in a previous paper. In this paper, we present a heuristic algorithm to solve these complex problems. With its straight forward approach, the algorithm can solve large-scale Quadratic Assignment Problems with reasonable computing times and efficient performance. Computational experience for solving many test examples is also presented. Author Affiliation: (a) AT&T, 111 Madison Avenue, Morristown, NJ 07960, USA (b) Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, MA 01003, USA Article Note: (footnote) This research was supported by National Science Foundation grant NSF #MSS-9116666.

The aim of this paper is to propose methods that incorporate equity concerns into cost utility analysis. The focus of the paper i.s on QALYs, but the results apply to health utility indices in general. Two interpretations of QALYs are considered: QALYs as (von Neumann Morgenstern) utilities and QALYs as measures of health. A justification is provided for aggregating consistently scaled "QALYs as utilities" over individuals. The conditions underlying unweighted aggregation of QALYs are identified. These conditions exclude two common types of equity concern. Algorithms are proposed that take into account equity concerns and that are relatively easy to apply. [ABSTRACT FROM AUTHOR]

Byline: Jinshyang Roan (a), Linguo Gong (b), Kwei Tang (b) Abstract: Setting the mean (target value) for a production process is an important decision for a producer when material cost is a significant portion of production cost. Because the process mean determines the process conforming rate, it affects other production decisions, including, in particular, production setup and raw material procurement policies. In this paper, we consider the situation in which the product of interest is assumed to have a lower specification limit, and the items that do not conform to the specification limit are scrapped with no salvage value. The production cost of an item is a linear function of the amount of the raw material used in producing the item, and the supply rate of the raw material is finite and constant. Furthermore, it is assumed that quantity discounts are available in the raw material cost and that the discounts are determined by the supply rate. Two types of discounts are considered in this paper: incremental quantity discounts and all-unit quantity discounts. A two-echelon model is formulated for a single-product production process to incorporate the issues associated with production setup and raw material procurement into the classical process mean problem. Efficient solution algorithms are developed for finding the optimal solutions of the model. Author Affiliation: (a) Department of Business Administration, Soochow University, Taipei, Taiwan, ROC (b) Department of Information Systems and Decision Sciences, Louisiana State University, Baton Rouge, LA 70 803, USA

Byline: Tim H. Hultberg (a), Domingos M. Cardoso (b) Abstract: A basic model of the task of assigning classes to professors, in such a way that the average number of distinct subjects assigned to each professor is minimized, is formulated as a mixed integer program. It turns out that the problem is a special case of the fixed charge transportation problem which in some cases corresponds to finding a basic solution of a transportation problem which is as degenerate as possible. We present an equivalent alternative formulation of the problem which makes it easy to prove that it is NP-hard in the strong sense and an exact branch and bound algorithm for its solution based on this alternative formulation is outlined. Computational experiments with data from a concrete problem, concludes the paper. Author Affiliation: (a) Department of Mathematics, University of Aveiro, Aveiro, Portugal (b) Department of Mathematics, University of Aveiro/INESC, Aveiro, Portugal Article History: Received 12 October 1994; Accepted 8 March 1996

A common but informal notion in social network analysis and other fields is the concept of a core/periphery structure. The intuitive conception entails a dense, cohesive core and a sparse, unconnected periphery. This paper seeks to formalize the intuitive notion of a core/periphery structure and suggests algorithms for detecting this structure, along with statistical tests for testing a priori hypotheses. Different models are presented for different kinds of graphs (directed and undirected, valued and nonvalued). In addition, the close relation of the continuous models developed to certain centrality measures is discussed. [ABSTRACT FROM AUTHOR]

In the paper a subquadratic (O (m), m is the number of arcs) triad census algorithm for large and sparse networks with small maximum degree is presented. The algorithm is implemented in the program Pajek. [ABSTRACT FROM AUTHOR]

Keywords Maintenance; Warranty; Minimal repair Abstract This paper investigates preventive-maintenance warranty (PMW) policies for repairable products. When the length of a warranty period is pre-specified, the optimal number of preventive maintenance actions, corresponding maintenance degrees, and the maintenance schedule are jointly determined. We show that there exists a unique optimal policy such that the expected total warranty cost is minimized. Under some reasonable conditions, structural properties of the optimal policy are obtained. Using these properties, an algorithm is provided to efficiently search for the optimal policy. In the case where the failure density is Weibull, a closed form expression of the optimal policy is derived. Finally, the impact of providing preventive maintenance within a warranty period is illustrated through a numerical example. Author Affiliation: Department of Industrial Management, National Taiwan University of Science and Technology, 43 Keelung Rd. Sec. 4, Taipei, Taiwan, ROC * Corresponding author. Tel.: +886-2-27376334; fax: +886-2-27376344 Article History: Received 16 June 2000; Accepted 6 September 2000 Byline: Ruey Huei Yeh [rhyeh@im.ntust.edu.tw], Hui-Chiung Lo

Keywords Heuristics; Local search; Simulated annealing; Unconstrained binary quadratic programming; Large-size problems Abstract The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported. Author Affiliation: Department of Information and Computer Engineering, Faculty of Engineering, Okayama University of Science, 1-1 Ridai-cho, Okayama 700-0005, Japan * Corresponding author. Tel.: +81-86-256-9527; fax: +81-86-255-3611 Article History: Received 25 January 2000; Accepted 7 September 2000 Byline: Kengo Katayama [katayama@ice.ous.ac.jp], Hiroyuki Narihisa

Keywords Goal programming; Multiobjective algorithm Abstract The (minimizing) achievement function of the traditional goal programming (GP) model has five basic forms: ni, pi, (ni+pi), (ni-pi), and (p.sub.i-n.sub.i), where n.sub.i and p.sub.i are nonnegative under and over achievement variables in the ith goal-constraint. This paper proposes and justifies three new objective-function forms: -ni, -pi, and (n.sub.i+p.sub.i) and presents an algorithm for solving the ensuing nonconvex program. We also introduce the intuitive concepts of the supposed indifference satisfactory interval (SISI), and the supposed indifference dissatisfactory interval (SIDI). We believe that these concepts will help the decision maker understand the different objective-function forms. Author Affiliation: (a) Economics and Management Department, Xi'an Petroleum Institute, Xi'an, Shaanxi Province 710065, People's Republic of China (b) The Joseph M. Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, PA 15260, USA * Corresponding author. Tel.: +1-412-648-1681; fax: +1-412-648-1693 Article History: Received 4 August 1999; Accepted 1 September 2000 Byline: Zhi Yong Zhang [zzyzhang@pub.xaonline.com] (a), Jen S. Shang [shang@katz.pitt.edu] (b)

Keywords Genetic algorithms; Product line design; Seller's return problem; Marketing. Abstract In this paper we deal with the product line design problem employing the seller's marginal return criterion. Because this problem is NP-Hard, many researchers proposed heuristic methods. We present a genetic algorithm (GA) based heuristic for solving the above problem. In the implementation, the GA is initialized in two different ways. In the first way, the GA is initialized with a random population. We call this algorithm GA1. In the second way, the solution of the beam search (BS) method is included in the first population of the GA. We call this algorithm GA2. We compare GA1, a recently developed BS method and GA2 on randomly generated problems. GA1 seems to be substantially better than the BS method in terms of CPU time. Also, the solutions found by GA1 are substantially better than those found by the BS method in comparable times. In many cases, GA2 improves the solution found by the BS method. Consequently, it is a good second step of the BS method. Author Affiliation: Department of Applied Informatics, University of Macedonia, Egnatia 156, POB 1591, Thessaloniki 54006, Greece * Corresponding author Article History: Received 26 March 1999; Accepted 20 July 2000 Byline: Georgia Alexouda [ageorgia@macedonia.uom.gr], Konstantinos Paparrizos [paparriz@macedonia.uom.gr]

Keywords Packing; Two-dimensional; Pallet loading; Heuristics Abstract This paper concerns the two-dimensional pallet loading problem (PLP), which requires the determination of the orthogonal layout that loads the maximum number of identical small rectangles (i.e., boxes or products) onto a large rectangle (i.e., pallet or container) without overlapping. Although many algorithms have been developed for this problem, the large amount of time required to find efficient layouts for a large PLP presents great practical difficulties. In this paper, we develop a heuristic that finds efficient layouts with low complexity. We also propose a new algorithm, using the heuristic as a sub-algorithm, which rapidly finds complicated solutions having a 5-block structure. Finally, computational results show that the new algorithm can be successfully applied to large PLPs with sizes exceeding 6800 boxes. Author Affiliation: Department of Industrial Engineering, Hanyang University, 1271 Sa 1 dong, Ansan, Kyounggi-do 425-791, South Korea * Corresponding author. Tel.: +82-31-4004068 Article History: Received 26 November 1999; Accepted 7 September 2000 Byline: Young-Gun G [geek@logistex.hanyang.ac.kr], Maing-Kyu Kang [dockang@logistex.hanyang.ac.kr]

In this paper we present a subdivision algorithm for the evaluation of the trigonometric spline curves with uniform knots. [Copyright &y& Elsevier]

In this paper, we present some iterative algorithms, mainly Schwarz algorithms, for an implicit two-sided obstacle problem. The monotonic convergence of the algorithms is proved. [Copyright &y& Elsevier]

In this paper, we introduce a new class of generalized co-complementarity problems in Banach spaces. An iterative algorithm for finding approximate solutions of these problems is considered. Some convergence results for this iterative algorithm are derived and several existence results are obtained. [Copyright &y& Elsevier]

In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded function technique. [Copyright &y& Elsevier]

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n). [Copyright &y& Elsevier]

Over the past few years, a continually increasing number of research efforts have investigated the application of evolutionary computation techniques for the solution of scheduling problems. Scheduling can pose extremely complex combinatorial optimization problems, which belong to the NP-hard family. Last enhancements on evolutionary algorithms include new multirecombinative approaches. Multiple Crossovers Per Couple (MCPC) allows multiple crossovers on the couple selected for mating and Multiple Crossovers on Multiple Parents (MCMP) do this but on a set of more than two parents. Techniques for preventing incest also help to avoid premature convergence. Issues on representation and operators influence efficiency and efficacy of the algorithm. The present paper shows how enhanced evolutionary approaches, can solve the Job Shop Scheduling Problem (JSSP) in single and multiobjective optimization. [Copyright &y& Elsevier]

Lists of if–then rules (i.e. ordered rule sets) are among the most expressive and intelligible representations for inductive learning algorithms. Two extreme strategies searching for such a list of rules can be distinguished: (i) local strategies primarily based on a step-by-step search for the optimal list of rules, and (ii) global strategies primarily based on a one-strike search for the optimal list of rules. Both approaches have their disadvantages. In this paper we present an intermediate strategy. A sequential covering strategy is combined with a one-strike genetic search for the next most promising rule. To achieve this, a new rule-fitness function is introduced. Experimental results on benchmark problems are presented and the performance of our intermediate approach is compared with other rule learning algorithms. Finally, GeSeCo''s performance is compared to a more local strategy on a set of tasks in which the information value of individual attributes is varied. [Copyright &y& Elsevier]

This paper presents a new fast front propagation algorithm for image segmentation. To approximate the partial differential equation (PDE) in level set algorithm, instead of moving the front in a small constant time step, the point with a minimum arrival time will be touched in one iteration. Only in a neighbourhood of this point, should the level set function be updated. Like the previously proposed level set methods, it is a robust method for image segmentation with capabilities to handle topological changes, significant protrusions and narrow regions. It is faster than the narrow band algorithm and more robust than the monotonically advancing scheme in image segmentation. The effectiveness and the capabilities of the algorithm were verified by simulated and real experiments. [Copyright &y& Elsevier]

For high-dimensional data, the appropriate selection of features has a significant effect on the cost and accuracy of an automated classifier. In this paper, a feature selection technique using genetic algorithms is applied. For classification, crisp and fuzzy k-nearest neighbor (kNN) classifiers are compared. Composite fuzzy classifier architectures are investigated. Experiments are conducted on airborne visible/infrared imaging spectrometer (AVIRIS) data, and the results are evaluated in the paper. [Copyright &y& Elsevier]

In this paper, we propose a wavelet decomposition approach for rotation-invariant template matching. In the matching process, we first decompose an input image into different multi-resolution levels in the wavelet-transformed domain, and use only the pixels with high wavelet coefficients in the decomposed detail subimage at a lower resolution level to compute the normalized correlation between two compared patterns. To make the matching invariant to rotation, we further use the ring-projection transform, which is invariant to object orientation, to represent an object pattern in the detail subimage. The proposed method significantly reduces the computational burden of the traditional pixel-by-pixel matching. Experimental results on a variety of real images have shown the efficacy of the proposed method. [Copyright &y& Elsevier]

The knowledge base of a probabilistic expert system is usually represented as a Bayesian network. Most of the knowledge engineering tools used in the development of probabilistic expert systems do not carry out the inference process directly over the network, but in a secondary graphical structure called a junction tree. The efficiency of inference (propagation) algorithms depends on the size of the junction tree obtained, and this size depends on the elimination sequence used during the compilation/transformation of the Bayesian network into a junction tree. The problem of searching for the best elimination sequence is an NP-hard problem [W. Wen, in: P. Bonissone, M. Henrion, L. Kanal and Z. Lemmer (Eds.), Uncertainty in Artificial Intelligence, vol. 6, North-Holland, Amsterdam, 1991, pp. 209–224], and this has motivated the proliferation of approximate methods to approach it (based variously on greedy heuristics, genetic algorithms, simulated annealing, etc.). In this paper we investigate the applicability to this problem of a new combinatorial optimization technique, inspired by a natural model, which has appeared recently: ant colony optimization [M. Dorigo, Optimization, learning and natural algorithms, Ph.D. thesis, Politecnico di Milano, Italy, 1992; M. Dorigo and L. Gambardella, IEEE Trans. Evol. Comput. 1 (1997) 53; M. Dorigo and G.Di. Caru, in: New Ideas in Optimization, McGraw-Hill, New York, 1999]. Our approach is validated by using a set of complex networks obtained from a repository. [Copyright &y& Elsevier]

Recently, a new image registration method, based on the Hausdorff fraction and a multi-resolution search of the transformation space, has been developed in the literature. This method has been applied to problems involving translations, translation and scale, and affine transformations. In this paper, we adapt the above method to the set of similarity transformations. We also introduce a new variant of the Hausdorff fraction similarity measure based on a multi-class approach, which we call the multi-class Hausdorff fraction (MCHF). The multi-class approach is more efficient because it matches feature points only if they are from the same class. To validate our approach, we segment edge maps into two classes which are the class of straight lines and the class of curves, and we apply the new multi-class approach to two image registration examples, using synthetic and real images, respectively. Experimental results show that the multi-class approach speeds up the multi-resolution search algorithm. [Copyright &y& Elsevier]

It is of utmost importance in multimedia processing to achieve still image segmentation, i.e., to partition images into regions of coherent color and texture. In this paper we propose a novel image segmentation method using a special visual descriptor. For each pixel p, the discrete cosine transform (DCT) of the block centered on p together with its location in the image is employed as its content descriptor thus resulting in a long vector v→p, referred to as situational DCT descriptors (SDDs). A scalar quantization step is then carried out on the DCT component of SDDs to reflect the fact that the human vision system is not of uniform discriminative sensitivity to details of different frequencies. Next the principal component analysis is conducted to drastically reduce the dimensionality of SDDs. The adaptive K-means algorithm is then performed to arrive at the region assignment for each pixel. The final partitioning results are obtained after performing the post-processing step. Encouraging empirical performance has been demonstrated. [Copyright &y& Elsevier]

This paper presents an automatic system for fire detection in video sequences. There are several previous methods to detect fire, however, all except two use spectroscopy or particle sensors. The two that use visual information suffer from the inability to cope with a moving camera or a moving scene. One of these is not able to work on general data, such as movie sequences. The other is too simplistic and unrestrictive in determining what is considered fire; so that it can be used reliably only in aircraft dry bays. We propose a system that uses color and motion information computed from video sequences to locate fire. This is done by first using an approach that is based upon creating a Gaussian-smoothed color histogram to detect the fire-colored pixels, and then using a temporal variation of pixels to determine which of these pixels are actually fire pixels. Next, some spurious fire pixels are automatically removed using an erode operation, and some missing fire pixels are found using region growing method. Unlike the two previous vision-based methods for fire detection, our method is applicable to more areas because of its insensitivity to camera motion. Two specific applications not possible with previous algorithms are the recognition of fire in the presence of global camera motion or scene motion and the recognition of fire in movies for possible use in an automatic rating system. We show that our method works in a variety of conditions, and that it can automatically determine when it has insufficient information. [Copyright &y& Elsevier]

The domination problem and its variants have been extensively studied in the literature. In this paper we investigate the domination problem in distance-hereditary graphs. In particular, we give a linear-time algorithm for the domination problem in distance-hereditary graphs by a labeling approach. We actually solve a more general problem, called the L-domination problem, which also includes the total domination problem as a special case. [Copyright &y& Elsevier]

In this paper, an implicit simulation code which can simulate a general three-dimensional sheet-metal forming is presented. An 8-node degenerated shell element is employed to approximate the continuous updated Lagrangian formulation of the global mechanical problem. Emphasis is put on expressing the contact conditions and taking into account the geometrical non-linearity. The characteristics of the authors’ contact algorithm is that the contact conditions just act as the boundary conditions of the FEM equations and need not be introduced into the stiffness matrix. Finally, two numerical examples demonstrating the effectiveness of the present approach are given. [Copyright &y& Elsevier]

A modified algorithm is introduced for computing the eigenvalues and the eigenvectors of a positive definite matrix using the inverse iteration method and the bimodal optical computer (BOC). It is known that the inverse iteration method is sensitive to the choice of the initial value of the eigenvalue. This paper investigates the effects of the initial choice of the eigenvalue on the solution using the inverse iteration method and suggests a modification. The modified algorithm presented in this paper uses the Rayliegh quotient ratio to compute a good estimate of the initial guess of an eigenvalue. A skyscraper eigenvalue problem is used as an example in this paper to help illustrate the new algorithm. [Copyright &y& Elsevier]

In this paper, the differential quadrature method is used to solve dynamic problems governed by second-order ordinary differential equations in time. The Legendre, Radau, Chebyshev, Chebyshev–Gauss–Lobatto and uniformly spaced sampling grid points are considered. Besides, two approaches using the conventional and modified differential quadrature rules to impose the initial conditions are also investigated. The stability and accuracy properties are studied by evaluating the spectral radii and truncation errors of the resultant numerical amplification matrices. It is found that higher-order accurate solutions can be obtained at the end of a time step if the Gauss and Radau sampling grid points are used. However, the conventional approach to impose the initial conditions in general only gives conditionally stable time step integration algorithms. Unconditionally stable algorithms can be obtained if the modified differential quadrature rule is used. Unfortunately, the commonly used Chebyshev–Gauss–Lobatto sampling grid points would not generate unconditionally stable algorithms. [Copyright &y& Elsevier]

When faced with high-dimensional data, one often uses principal component analysis (PCA) for dimension reduction. Classical PCA constructs a set of uncorrelated variables, which correspond to eigenvectors of the sample covariance matrix. However, it is well-known that this covariance matrix is strongly affected by anomalous observations. It is therefore necessary to apply robust methods that are resistant to possible outliers.Li and Chen [J. Am. Stat. Assoc. 80 (1985) 759] proposed a solution based on projection pursuit (PP). The idea is to search for the direction in which the projected observations have the largest robust scale. In subsequent steps, each new direction is constrained to be orthogonal to all previous directions. This method is very well suited for high-dimensional data, even when the number of variables p is higher than the number of observations n. However, the algorithm of Li and Chen has a high computational cost. In the references [C. Croux, A. Ruiz-Gazen, in COMPSTAT: Proceedings in Computational Statistics 1996, Physica-Verlag, Heidelberg, 1996, pp. 211–217; C. Croux and A. Ruiz-Gazen, High Breakdown Estimators for Principal Components: the Projection-Pursuit Approach Revisited, 2000, submitted for publication.], a computationally much more attractive method is presented, but in high dimensions (large p) it has a numerical accuracy problem and still consumes much computation time.In this paper, we construct a faster two-step algorithm that is more stable numerically. The new algorithm is illustrated on a data set with four dimensions and on two chemometrical data sets with 1200 and 600 dimensions. [Copyright &y& Elsevier]

Synthetic Aperture Radar (SAR) is a well-established technique for air- and spaceborne high resolution imaging. This paper demonstrates the phase preservation of the new Frequency Scaling Algorithm for Spotlight SAR data processing and investigates differences between Stripmap and Spotlight illumination. The algorithm performs the range cell migration correction for non-chirped raw data without interpolation by using a novel frequency scaling operation. The azimuth processing is based on a spectral analysis approach that is made highly accurate by azimuth scaling. In almost all processing stages, a subaperture approach is introduced for efficient azimuth processing. The maximum scene size for air- and spaceborne spotlight parameter examples is estimated. A method is proposed, which shows how to process Stripmap mode raw data in the Spotlight mode. Point target simulations and real raw data processing, including the generation of Spotlight interferograms prove the phase preservation of the Frequency Scaling Algorithm. The same SAR Stripmap raw data set of DLR''s airborne system is processed in Stripmap and in Spotlight mode and the resulting detected images and interferograms are compared to each other. The differences due to the different range of squint angles used for the azimuth focusing are discussed. [Copyright &y& Elsevier]

The Delaunay triangulations of a set of points are a class of triangulations which play an important role in a variety of different disciplines of science. Regular triangulations are a generalization of Delaunay triangulations that maintain both their relationship with convex hulls and with Voronoi diagrams. In regular triangulations, a real value, its weight, is assigned to each point.In this paper a simple data structure is presented that allows regular triangulations of sets of points to be dynamically updated, that is, new points can be incrementally inserted in the set and old points can be deleted from it. The algorithms we propose for insertion and deletion are based on a geometric interpretation of the history data structure in one more dimension and use lifted flips as the unique topological operation. This results in rather simple and efficient algorithms. The algorithms have been implemented and experimental results are given. [Copyright &y& Elsevier]

This paper presents a new representation for the implicit equation of a planar rational curve with high order singularity by using moving curves technique. The new representation is the determinant of a matrix which is less than one half the size of the conventional expression based on the Bezout''s resultant. An efficient algorithm to compute the new representation is derived, and comparisons for the computational costs between various resultant based methods are made. The results show that the implicit representation developed in this paper is not only more compact but also much more efficient to compute the implicit equation of the rational curve than previous methods. [Copyright &y& Elsevier]

This paper addresses the theoretical development and numerical implementation of energy consistent algorithms for dynamic elastoplasticity, emphasizing finite strain constitutive formulations so that unconditional stability of the algorithms is assured even in the fully nonlinear regime. The key concept behind energy consistency is the requirement that the discretized system obey an a priori stability estimate, which may be derived in general using the first and second laws of thermodynamics. This approach to computational dynamic plasticity differs from typical application of traditional algorithms (such as Newmark or Hilber–Hughes–Taylor-α methods), where local time integration schemes for plasticity laws are developed somewhat independently from the global time integration scheme for the equations of motion, without explicit consideration of thermodynamical restrictions. Two algorithms based on both additive and multiplicative finite deformation plasticity model are formulated within the energy consistent framework. Both algorithms possess the desirable feature of nonlinear stability of previous energy–momentum algorithms for elastodynamics. [Copyright &y& Elsevier]