A new algorithm for solving the tree isomorphism problem

The problem and known algorithms for its solution are briefly discussed. An efficient algorithm for canonical coding of unlabelled trees is described. Several applications of the code, including the tree isomorphism problem, are considered. Efficiency of the algorithm is evaluated and discussed.     

A parametric filtering algorithm for the graph isomorphism problem

We introduce a new filtering algorithm, called IDL(d)-filtering, for a global constraint dedicated to the graph isomorphism problem—the goal of which is to decide if two given graphs have an identical structure. The basic idea of IDL(d)-filtering is to label every vertex with respect to its relationships with other vertices around it in the graph, and to use these labels to filter domains by removing values that have different labels. IDL(d)-filtering is parameterized by a positive integer value d which gives a limit on the distance between a vertex to be labelled and the set of vertices considered to build its label. We experimentally compare different instantiations of IDL(d)-filtering with state-of-the-art dedicated algorithms and show that IDL(d)-filtering is more efficient on regular sparse graphs and competitive on other kinds of graphs.     

A combinatorial approximation algorithm for concurrent flow problem and its application

The multi-commodity flow problem involves simultaneous shipping several different commodities from sources to sinks in a directed network with total amount of flow going through an edge limited by its capacity. The optimization version of the multi-commodity flow problem is the maximum concurrent flow problem, which finds a flow with the minimum congestion. For any positive ε, the ε-optimal concurrent flow problem is to find a solution whose the congestion value is no more than (1+ε) times the minimum congestion. In recent years, a few fast combinatorial approximation algorithms for the ε-optimal concurrent flow problem have been presented. In this paper we propose a new variant of the combinatorial approximation algorithm: CACF with a tighter computation bound in decreasing the values of congestion and the potential function. Numerical comparisons are made between the results obtained by the combinatorial approximation algorithms and those did by the linear programming package CPLEX on large-scale test networks. The application of CACF to efficiently solving the system-optimal network flow problem is given where good results have been obtained. It has shown the capacity of the CACF in dealing with problems of concurrent flow associated.     

A graph isomorphism algorithm for object recognition

We present an algorithm to solve the graph isomorphism problem for the purpose of object recognition. Objects, such as those which exist in a robot workspace, may be represented by labelled graphs (graphs with attributes on their nodes and/or edges). Thereafter, object recognition is achieved by matching pairs of these graphs. Assuming that all objects are sufficiently different so that their corresponding representative graphs are distinct, then given a new graph, the algorthm efficiently finds the isomorphic stored graph (if it exists). The algorithm consists of three phases: preprocessing, link construction, and ambiguity resolution. Results from experiments on a wide variety and sizes of graphs are reported. Results are also reported for experiments on recognising graphs that represent protein molecules. The algorithm works for all types of graphs except for a class of highly ambiguous graphs which includes strongly regular graphs. However, members of this class are detected in polynomial time, which leaves the option of switching to a higher complexity algorithm if desired.     

A new algorithm for error-tolerant subgraph isomorphism detection

We propose a new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph. The algorithm is based on a compact representation of the model graphs. This representation is derived from the set of model graphs in an off-line preprocessing step. The main advantage of the proposed representation is that common subgraphs of different model graphs are represented only once. Therefore, at run time, given an unknown input graph, the computational effort of matching the common subgraphs for each model graph onto the input graph is done only once. Consequently, the new algorithm is only sublinearly dependent on the number of model graphs. Furthermore, the new algorithm can be combined with a future cost estimation method that greatly improves its run-time performance     

A subgraph isomorphism algorithm using resolution

An efficient algorithm for subgraph isomorphism is presented. It combines tree search with relaxation by using resolution. Bitwise parallelism, which is an important factor in speed, is achieved during the resolution process even though a sequential computer is used. The algorithm can be easily modified to apply to multi-relation labeled graphs, attributed graphs and some higher order structures such as arrangements.     

A polynomial algorithm for submap isomorphism of general maps

Combinatorial maps explicitly encode orientations of edges around vertices, and have been used in many fields. In this paper, we address the problem of searching for patterns in model maps by putting forward the concept of symbol graph. A symbol graph will be constructed and stored for each model map in the preprocessing. Furthermore, an algorithm for submap isomorphism is presented based on symbol sequence searching in the symbol graphs. The computational complexity of this algorithm is quadratic in the worst case if we neglect the preprocessing step.     

求解图同构的判定算法

图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决。受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件：在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性。     

Graph isomorphism: A heuristic edge-partitioning-oriented algorithm

A new algorithm for testing isomorphism on directed and undirected graphs is described. It consists of an 0 (n ⁵) algorithm for partitioning node and edge sets, plus a heuristic procedure for deriving all the isomorphisms. The partitioning is described by a “connectivity graph” on which a sufficient condition for isomerphism can be tested.     

On the isomorphism problem of concept algebras

Weakly dicomplemented lattices are bounded lattices equipped with two unary operations to encode a negation on concepts. They have been introduced to capture the equational theory of concept algebras (Wille 2000; Kwuida 2004). They generalize Boolean algebras. Concept algebras are concept lattices, thus complete lattices, with a weak negation and a weak opposition. A special case of the representation problem for weakly dicomplemented lattices, posed in Kwuida (2004), is whether complete weakly dicomplemented lattices are isomorphic to concept algebras. In this contribution we give a negative answer to this question (Theorem 4). We also provide a new proof of a well known result due to M.H. Stone (Trans Am Math Soc 40:37–111, 1936), saying that each Boolean algebra is a field of sets (Corollary 4). Before these, we prove that the boundedness condition on the initial definition of weakly dicomplemented lattices (Definition 1) is superfluous (Theorem 1, see also Kwuida (2009)).     

A hybrid rendering algorithm for textile objects

Although realistic textile rendering has been widely used in virtual garment and try-on systems, a robust method to simulate textile with a realistic appearance and high fidelity is yet to be established. We propose to use a novel hybrid geometric- and image-based rendering (GIBR) method to achieve photo realistic representation of textile products. The image-based technique, with its radiance synthesis algorithm, enables us to recover the reflectance properties of textile in an environment photo, and thus can render the appearance of textile material. The geometry-based technique, with its traditional illumination model of assigning illumination parameters extracted from the original scene (such as radiance and chroma dispatch), makes it possible to interactively manipulate 3D virtual objects in the “real” environment. Our realistic textile rendering method has advantages over the traditional ones in its easiness to implement and its wide range of applications.     

A (sub)graph isomorphism algorithm for matching large graphs

We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs.     

An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem

This paper presents an improved ant colony optimization algorithm (IACO) for solving mobile agent routing problem. The ants cooperate using an indirect form of communication mediated by pheromone trails of scent and find the best solution to their tasks guided by both information (exploitation) which has been acquired and search (exploration) of the new route. Therefore the premature convergence probability of the system is lower. The IACO can solve successfully the mobile agent routing problem, and this method has some excellent properties of robustness, self-adaptation, parallelism, and positive feedback process owing to introducing the genetic operator into this algorithm and modifying the global updating rules. The experimental results have demonstrated that IACO has much higher convergence speed than that of genetic algorithm (GA), simulated annealing (SA), and basic ant colony algorithm, and can jump over the region of the local minimum, and escape from the trap of a local minimum successfully and achieve the best solutions. Therefore the quality of the solution is improved, and the whole system robustness is enhanced. The algorithm has been successfully integrated into our simulated humanoid robot system which won the fourth place of RoboCup2008 World Competition. The results of the proposed algorithm are found to be satisfactory.     

A new co-evolutionary decomposition-based algorithm for bi-level combinatorial optimization

Bi-Level Optimization Problems (BLOPs) are a class of challenging problems with two levels of optimization tasks. The main goal is to optimize the upper level problem which has another optimization problem as a constraint. The latter is called the lower level problem. In this way, the evaluation of each upper level solution requires finding an (near) optimal solution to the corresponding lower level problem, which is computationally very expensive. Many real world applications are bi-level by nature, ranging from logistics to software engineering. Further, proposed bi-level approaches have been restricted to solve linear BLOPs. This fact has attracted the evolutionary computation community to tackle such complex problems and many interesting works have recently been proposed. Unfortunately, most of these works are restricted to the continuous case. Motivated by this observation, we propose in this paper a new Co-evolutionary Decomposition Algorithm inspired from Chemical Reaction Optimization algorithm, called E-CODBA (Energy-based CODBA), to solve combinatorial bi-level problems. Our algorithm is based on our previous works within this research area. The main idea behind E-CODBA is to exploit co-evolution, decomposition, and energy laws to come up with good solution(s) within an acceptable execution time. The statistical analysis of the experimental results on the Bi-level Multi-Depot Vehicle Routing Problem (Bi-MDVRP) show the out-performance of our E-CODBA against four recently proposed works in terms of effectiveness and efficiency.     

Exhaustive generation of combinatorial objects by ECO

The problem of exhaustively generating combinatorial objects can currently be applied to many disciplines, such as biology, chemistry, medicine and computer science. A well known approach to the exhaustive generation problem is given by the Gray code scheme for listing n-bit binary numbers in such a way that successive numbers differ in exactly one bit position. In this work, we introduce an exhaustive generation algorithm, which is general for the classes of succession rules considered in [1]. We also show that our algorithm is efficient in an amortized sense; it actually uses only a constant amount of computation per object.Received: 10 October 2003, Revised: 10 February 2004, Published online: 21 April 2004     

基于多步回溯Q学习的自动发电控制指令动态优化分配算法

单步Q学习在火电占优、机组时延较大的A动发电控制(AGC)功率指令动态优化分配中的应用表现出收敛速度慢等不足而影响最优策略的获取.具有多步预见能力的多步回溯Q学习(Q(λ))显式利用资格迹进行高效回溯操作,能够有效解决火电机组大时滞环节带来的延时回报问题,算法平均收敛时间较Q学习缩短50%以上.算法奖励函数引入调节费用...