% BibTeX database subiso.bib % exported by BibGene 1.2.2, Wed, May 16, 2001. @inproceedings{Abb-CSC-75, title = {{GRIPHOS as a relational data base model}}, author = {S. Abbey}, booktitle = {Proc. Computer Science Conference}, publisher = {Assoc. Comput. Mach.}, pages = {44}, year = {1975}, abstract = {Most Information Retrieval Systems (IRS) that have been implemented to date have many restrictions imposed on the user for the convenience of the system programmer. Among these restrictions two common ones are (1) requiring the user to declare the structure of all the records beforehand, and (2) requiring the user to maintain a detailed knowledge of these structures at query time. A design for an IRS is proposed in which both of these problems are alleviated. A Relational Data Base System in the style of Codd's work is described that allows the data itself to define the structure of each stored record differently from every other record. At query time, the user is not required to have any knowledge of these structures, but merely be aware of the relationships that exist between the various data items. These relationships may be represented as a digraph, where the nodes model the data items, and the edges model the relationships. With this model, a query is equivalent to finding a given subgraph of a graph.}} @unpublished{Abd-95, title = {{Parallel implementation of graph matching for object recognition}}, author = {M. A. Abdulrahim}, year = {1995}, url = {http://ppl.mines.colorado.edu/mohd/proj.html}, note = {Student project for course MACS 440/563, Parallel Computing for Scientists and Engineers, Colorado School of Mines, 1995, under the supervision of M. Misra}} @inproceedings{AdhPen-WADS-89, title = {{Parallel algorithms for cograph recognition and applications}}, author = {G. S. Adhar and S. Peng}, booktitle = {Proc. 1st Worksh. Algorithms and Data Structures}, number = {382}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {335--351}, year = {1989}, abstract = {Cographs arise in application areas such as examination scheduling and automatic clustering of index terms. It is shown that recognition, transitive orientation, maximum node weighted clique, minimum node coloring, minimum weight dominating set, minimum fill-in and isomorphism for cographs is in NC. The model of computation is CRCW P-RAM.}} @inproceedings{AkiWon-CCVPR-83, title = {{A new product graph based algorithm for subgraph isomorphism}}, author = {F. A. Akinniyi and A. K. C. Wong}, booktitle = {Proc. Conf. Computer Vision and Pattern Recognition}, publisher = {Inst. Electrical {\&} Electronics Engineers}, pages = {457--467}, year = {1983}, abstract = {Presents a new algorithm for detecting graph isomorphisms for pairs of graphs. The algorithm entails a tree searching procedure over the projections of the implicit product of the two graphs. It utilizes the minimum number of neighbours of the projected graphs to detect infeasible subtrees. Its efficient storage space utilisation and low average running time are particularly advantageous.}} @inproceedings{AkiWon-ICCS-82, title = {{A graph monomorphism algorithm}}, author = {F. A. Akinniyi and A. K. C. Wong}, booktitle = {Proc. Int. Conf. Cybernetics and Society}, publisher = {Inst. Electrical {\&} Electronics Engineers}, pages = {472--476}, year = {1982}, abstract = {Presents a new algorithm for detecting subgraph isomorphism for pairs of graphs. The algorithm entails a tree searching procedure over the projections of the implicit product of the two graphs. It uses the minimum number of neighbours of the projected graphs to eliminate infeasible subtrees. It is efficient in its storage space and running time. It has also overcome a problem of intrinsic ambiguity when a cyclic structure prevails.}} @article{AkiWonSta-TSMC-86, title = {{A new algorithm for graph monomorphism based on the projections of the product graph}}, author = {F. A. Akinniyi and A. K. C. Wong and D. A. Stacey}, journal = {Trans. Systems, Man and Cybernetics}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {SMC-16}, pages = {740--751}, year = {1986}, abstract = {An algorithm is presented for detecting graph monomorphisms for a pair of graphs. The algorithm entails a tree search based on the projections of the product graph called the net of the two graphs. It uses the minimum number of neighbors of the projected graphs to detect infeasible subtrees. The algorithm, in comparison with that of Deo et al. (1977), is more efficient in its storage space utilization and average execution time. It does not suffer from the ambiguity which arises in Deo et al.'s work when cycle graphs are matched. Applications to attributed graph monomorphisms are included.}} @inproceedings{Aku-CPM-93, title = {{A linear time pattern matching algorithm between a string and a tree}}, author = {T. Akutsu}, booktitle = {Proc. 4th Symp. Combinatorial Pattern Matching}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {1--10}, year = {1993}, abstract = {We describe a linear time algorithm for testing whether or not there is a path of a tree $T$ ($|V(T)|=n$) that coincides with a string $s$ ($|s|=m$). In the algorithm, $O(n/m)$ vertices are selected from $V(T)$ such that any path of length more than $m-2$ must contain at least one of the selected vertices. A search is performed using the selected vertices as `bases'. A suffix tree is used effectively in the algorithm. Although the size of the alphabet is assumed to be bounded by a constant, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to $O(n\log n)$.}} @article{Aku-TFECCS-92, title = {{An NC algorithm for computing canonical forms of graphs of bounded separator}}, author = {T. Akutsu}, journal = {IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences}, volume = {E75-A}, pages = {512--514}, year = {1992}, abstract = {Lingas (1988) developed an NC algorithm for subgraph isomorphism for connected graphs of bounded separator and bounded valence. The author presents an NC algorithm for computing canonical forms of graphs of bounded separator using a similar technique.}} @article{Aku-TFECCS-93, title = {{A Polynomial Time Algorithm for Finding a Largest Common Subgraph of almost Trees of Bounded Degree}}, author = {T. Akutsu}, journal = {IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences}, volume = {E76-A}, number = {9}, year = {1993}, abstract = {This paper considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. A graph is called an almost tree if mod E(B) mod {$<$}or= mod V(B) mod +K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K{$>$}or=O if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to this problem.}} @article{Aku-TIS-92, title = {{An RNC algorithm for finding a largest common subtree of two trees}}, author = {T. Akutsu}, journal = {IEICE Trans. Information and Systems}, volume = {E75-D}, pages = {95--101}, year = {1992}, abstract = {It is known that the problem of finding a largest common subgraph is NP-hard for general graphs even if the number of input graphs is two. It is also known that the problem can be solved in polynomial time if the input is restricted to two trees. The paper presents a randomized parallel (an RNC) algorithm for finding a largest common subtree of two trees. The dynamic tree contraction technique and the RNC minimum weight perfect matching algorithm are used to obtain the RNC algorithm. Moreover, an efficient NC algorithm is presented in the case where input trees are of bounded vertex degree. It works in $O(\log(n_1)+\log(n_2))$ time using $O(n_1 n_2)$ processors on a CREW PRAM where $n_1$ and $n_2$ denote the numbers of vertices of input trees. It is also proved that the problem is NP-hard if the number of input trees is more than two. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem of finding a largest common subtree of three trees.}} @inproceedings{AkuHal-ISAAC-94, title = {{On the approximation of largest common subtrees and largest common point sets}}, author = {T. Akutsu and Magn{\'u}s M. Halld{\'o}rsson}, booktitle = {Proc. 5th Int. Symp. Algorithms and Computation}, number = {834}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {405--413}, year = {1994}, abstract = {This paper considers the approximability of the largest common subtree and the largest common subgraph problems, which have applications in molecular biology. It is shown that approximating the problems within a factor of $n^\epsilon$ is NP-complete, while a general search algorithm which approximates both problems within a factor of $O(n/\log{n})$ is presented. Moreover, several variants of the largest common subtree problem are studied.}} @article{Alm-AMM-91, title = {{A polynomial transform for matching pairs of weighted graphs}}, author = {H. A. Almohamad}, journal = {Applied Math. Modeling}, volume = {15}, pages = {216--222}, year = {1991}} @article{AlmDuf-PAMI-93, title = {{A linear programming approach for the weighted graph matching problem}}, author = {H. A. Almohamad and S. O. Duffuaa}, journal = {Trans. Pattern Analysis and Machine Intelligence}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {15}, pages = {522--525}, year = {1993}, abstract = {A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in $L_1$ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a Simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is $O(n^6 L)$ for matching graphs of size $n$. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods.}} @inproceedings{AloSeyTho-STOC-90, title = {{A separator theorem for graphs with an excluded minor and its applications}}, author = {Noga Alon and Paul D. Seymour and Robin Thomas}, booktitle = {Proc. 22nd Symp. Theory of Computing}, publisher = {Assoc. Comput. Mach.}, pages = {293--299}, year = {1990}, abstract = {Let $G$ be an $n$-vertex graph with nonnegative weights whose sum is $1$ assigned to its vertices, and with no minor isomorphic to a given $h$-vertex graph $H$. The authors prove that there is a set $X$ of no more than $h^{3/2}n^{1/2}$ vertices of $G$ whose deletion creates a graph in which the total weight of every connected component is at most $1/2$. They exhibit an algorithm which finds, given an $n$-vertex graph $G$ with weights as above and an $h$-vertex graph $H$, either such a set $X$ or a minor of $G$ isomorphic to $H$. The algorithm runs in time $O(h^{1/2}n^{1/2}m)$, where $m$ is the number of edges of $G$ plus the number of its vertices. The authors' results supply extensions of the many known applications of the Lipton-Tarjan separator theorem (1979,1980) from the class of planar graphs (or that of graphs with bounded genus) to any class of graphs with an excluded minor. For example, it follows that for any fixed graph $H$, given a graph $G$ with $n$ vertices and with no $H$-minor one can approximate the size of the maximum independent set of $G$ up to a relative error of $1/\sqrt{\log{n}}$ in polynomial time, find that size exactly and find the chromatic number of $G$ in time $2^{O(\sqrt{n})}$ and solve any sparse system of $n$ linear equations in $n$ unknowns whose sparsity structure corresponds to $G$ in time $O(n^{3/2})$. They also describe a combinatorial application of the result which relates the tree-width of a graph to the maximum size of a $K_h$-minor in it.}} @inproceedings{AloYusZwi-ESA-94, title = {{Finding and Counting Given Length Cycles}}, author = {Noga Alon and R. Yuster and U. Zwick}, booktitle = {Proc. 2nd Eur. Symp. Algorithms}, number = {855}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, year = {1994}, abstract = {We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the graph in question, and not on the number of vertices. The bounds obtained improve upon various previously known results.}} @article{AloYusZwi-JACM-95, title = {{Color-coding}}, author = {Noga Alon and R. Yuster and U. Zwick}, journal = {J. Assoc. Comput. Mach.}, volume = {42}, number = {4}, pages = {844--856}, month = {July}, year = {1995}} @inproceedings{AloYusZwi-STOC-94, title = {{Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs}}, author = {Noga Alon and R. Yuster and U. Zwick}, booktitle = {Proc. 26th Symp. Theory of Computing}, publisher = {Assoc. Comput. Mach.}, pages = {326--335}, year = {1994}, abstract = {We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length $k$, and other small subgraphs, within a given graph $G=(V, E)$. The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method we obtain, among others, the following new results: for every fixed $k$, if a graph $G=(V, E)$ contains a simple cycle of size exactly $k$, then such a cycle can be found in either $O(V^\omega)$ expected time or $O(V^\omega\log{V})$ worst-case time, where $\omega<2.376$ is the exponent of matrix multiplication. (Here and in what follows we use $V$ and $E$ instead of $|V|$ and $|E|$ whenever no confusion may arise.) For every fixed $k$, if a planar graph $G=(V, E)$ contains a simple cycle of size exactly $k$, then such a cycle can be found in either $O(V)$ expected time or $O(V\log{V})$ worst-case time. The same algorithm applies, in fact, not only to planar graphs, but to any minor closed family of graphs which is not the family of all graphs. If a graph $G=(V, E)$ contains a subgraph isomorphic to a bounded tree-width graph $H=(V_H,E_H)$ where $|V_H|=O(\log{V})$, then such a copy of $H$ can be found in polynomial time. This was not previously known even if $H$ were just a path of length $O(\log{V})$. These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture that the LOG PATH problem is in P. We can even show that the LOG PATH problem is in NC.}} @inproceedings{AndNolSch-WG-94, title = {{Cartesian products of graphs as spanning subgraphs of de Bruijn graphs}}, author = {T. Andreae and M. Nolle and G. Schreiber}, booktitle = {Proc. 20th Int. Worksh. Graph-Theoretic Concepts in Computer Science}, number = {903}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {140--150}, year = {1994}, abstract = {For Cartesian products $G=G_1\times\ldots\times G_m$ ($m\ge 2$) of nontrivial connected graphs $G_i$ and the $n$-dimensional base $B$ de Bruijn graph $D=D_B(n)$, the authors investigate whether or not there exists a spanning subgraph of $D$ which is isomorphic to $G$. The authors show that $G$ is never a spanning subgraph of $D$ when $n$ is greater than three or when $n$ equals three and $m$ is greater than two. For $n=3$ and $m=2$, the authors can show for wide classes of graphs that $G$ cannot be a spanning subgraph of $D$. In particular, these non-existence results imply that $D_B(n)$ never contains a torus (i.e., the Cartesian product of $m\ge 2$ cycles) as a spanning subgraph when $n$ is greater than two. For $n=2$ the situation is quite different: the authors present a sufficient condition for a Cartesian product $G$ to be a spanning subgraph of $D=D_B(2)$. As one of the corollaries the authors obtain that a torus $G=G_1\times\ldots\times G_m$ is a spanning subgraph of $D=D_B(2)$ provided that $|G|=|D|$ and that the $G_i$ are even cycles of length $\ge 4$. In addition the authors apply their results to obtain embeddings of relatively small dilation of popular processor networks (tori, meshes and hypercubes) into de Bruijn graphs of fixed small base.}} @article{AngVal-JCSS-79, title = {{Fast probabilistic algorithms for Hamiltonian circuits and matchings}}, author = {Dana Angluin and L. G. Valiant}, journal = {J. Computer {\&} System Sciences}, volume = {18}, pages = {155--193}, year = {1979}, abstract = {The authors describe and analyse three simple efficient algorithms with good probabilistic behaviour: two algorithms with run times of $O(n(\log{n})^2)$ which almost certainly find directed (undirected) Hamiltonian circuits in random graphs of at least $cn\log{n}$ edges, and an algorithm with a run time of $O(n\log{n})$ which almost certainly finds a perfect matching in a random graph of at least $cn\log{n}$ edges. Auxiliary propositions regarding conversion between input distributions and the 'de-randomization' of randomized algorithms are proved. A model, the random access computer (RAC), is introduced specifically to treat run times in low-level complexity.}} @article{AraFukKad-IECEJ-85, title = {{An automatic chip assignment based on the subgraph isomorphism}}, author = {H. Arai and Y. Fukazawa and T. Kadokura}, journal = {Trans. Inst. Electronics and Communication Engineers of Japan D}, volume = {J68D}, pages = {2162--2164}, year = {1985}, abstract = {An algorithm which assigns IC chips to a given description of a hardware is described. This algorithm is based on the subgraph isomorphism between a chip graph and a hardware graph. The main advantage of this algorithm is the early discovery of the non-isomorphism of two graphs.}, note = {In Japanese}} @article{AraYamHir-IECEJ-85, title = {{Lower bounds on the time complexity for some subgraph detection problems}}, author = {M. Arai and M. Yamashita and T. Hirata and T. Ibaraki and N. Honda}, journal = {Trans. Inst. Electronics and Communication Engineers of Japan D}, volume = {J68D}, pages = {1735--1743}, year = {1985}, note = {In Japanese}} @article{AraYamHir-SCJ-86, title = {{Lower bounds on the time complexity for some subgraph detection problems}}, author = {M. Arai and M. Yamashita and T. Hirata and T. Ibaraki and N. Honda}, journal = {Systems and Computers in Japan}, volume = {17}, pages = {95--102}, year = {1986}, abstract = {The authors derive non-trivial lower bounds on the time complexity of some subgraph detection problems, for the computational model based on a decision tree. Let $\pi$ be a property that is closed under isomorphism, and satisfies a certain degree of constraint. Then it is shown that the problems of finding a subgraph with property $\pi$ and with the total edge weight equal to $1$ has $\Omega(n^3\log{n})$ time lower bounds, where $n$ is the number of nodes. This is an extension of the result proved by Nakayama et al. (1983). In addition, the authors present the proof for a lower bounds $\Omega(n^3)$ when property $\pi$ is clique.}} @article{ArnCorPro-SJADM-87, title = {{Complexity of finding embeddings in a $k$-tree}}, author = {Stefan Arnborg and D. G. Corneil and A. Proskurowski}, journal = {SIAM J. Algebraic and Discrete Methods}, volume = {8}, pages = {277--284}, year = {1987}} @inproceedings{ArnProSee-CSL-90, title = {{Monadic second order logic, tree automata and forbidden minors}}, author = {Stefan Arnborg and A. Proskurowski and D. Seese}, booktitle = {Proc. 4th Worksh. Computer Science Logic}, publisher = {Springer-Verlag}, pages = {1--16}, year = {1990}, abstract = {N. Robertson and P. D. Seymour (1986) proved that each minor closed class $K$ of graphs is characterised by finitely many minimal forbidden minors. If these minors are given then they can be used to find an efficient membership test for such classes. From these minors one can get a monadic second order description of the class $K$. The main result of the article is that from a monadic second order description of $K$ the minimal forbidden minors can he constructed, when $K$ contains only graphs of universally bounded tree width. The result is applied to the class of partial 2-paths.}} @article{ArtBatGri-JCICS-92, title = {{Similarity searching in databases of three-dimensional molecules and macromolecules}}, author = {P. J. Artymiuk and P. A. Bath and H. M. Grindley and C. A. Pepperrell and A. R. Poirrette and D. W. Rice and D. A. Thorner and D. J. Wild and P. Willett and F. H. Allen and R. Taylor}, journal = {J. Chemical Information and Computer Sciences}, volume = {32}, pages = {617--630}, year = {1992}, abstract = {This paper discusses algorithmic techniques for measuring the degree of similarity between pairs of three-dimensional (3-D) chemical molecules represented by interatomic distance matrices. A comparison of four methods for the calculation of 3-D structural similarity suggests that the most effective one is a procedure that identifies pairs of atoms, one from each of the molecules that are being compared, that lie at the center of geometrically-related volumes of 3-D space. This atom mapping method enabled the calculation of a wide range of types of intermolecular similarity coefficient, including measures that are based on physicochemical data. Massively-parallel implementations of the method are discussed, using the AMT Distributed Array Processor. Current work involves the use of angular information and the extension of the method to field-based similarity searching. Similarity searching in 3-D macromolecules is effected by the use of a maximal common subgraph (MCS) isomorphism algorithm with a novel, graph-based representation of the tertiary structures of proteins. This algorithm is being used to identify similarities between the 3-D structures of proteins in the Brookhaven Protein Data Bank; its use is exemplified by searches involving the NAD-binding fold motif.}} @article{ArtGriPoi-JCICS-94, title = {{Identification of beta-sheet motifs, of psi-loops, and of patterns of acid residues in three-dimensional protein structures using a subgraph-isomorphism algorithm}}, author = {P. J. Artymiuk and H. M. Grindley and A. R. Poirrette and D. W. Rice and E. C. Ujah and P. Willett}, journal = {J. Chemical Information and Computer Sciences}, volume = {34}, pages = {54--62}, year = {1994}, abstract = {Discusses the use of graph-theoretical techniques for the representation and searching of 3D protein structures that are represented by labeled graphs. Two types of graph are considered. The nodes in the first type of chemical graph describe the secondary-structure elements and the edges describe the geometric relationships between pairs of these elements. The use of Ullmann's (1976) subgraph isomorphism algorithm with these representations permits the identification of all occurrences of all possible beta -sheet motifs in a 114-protein subset of the Protein Data Bank. A binary notation is used to describe the parallel or antiparallel characters of adjacent strands in a sheet, and it is shown that very few of the possible types of sheet are found to occur in practice. Similar conclusions are obtained using a more detailed notation that includes the sheets' topological connectivities. The latter notation enables searches to be carried out for psi -loops and allows the identification of 20 proteins that had not previously been known to contain this type of loop. The nodes in the second type of protein graph describe the amino acid residues in protein structures and the edges the geometric relationships between pairs of these residues. The use of the Ullmann algorithm with these representations permits the identification of the occurrences of patterns of residues. The identification process is illustrated by means of searches for the two aspartate groups that are known to be involved in the catalytic mechanism of the aspartic proteinases.}} @article{Asa-ISCS-85, title = {{An approach to the subgraph homeomorphism problem and the max-cut problem}}, author = {Tetsuo Asano}, booktitle = {Proc. Int. Symp. Circuits and Systems}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {3}, pages = {1657--1660}, year = {1985}, abstract = {Two efficient algorithms are presented: One is an $O(|V|)$-time algorithm to determine whether a given graph $G=(V,E)$ has a subgraph homeomorphic to the Kuratowski graph $K(3,3)$ and the other is an $O(|V|^3)$-time algorithm to find a maximum cut of a given graph $G=(V,E)$ without subgraphs homeomorphic to $K(3,3)$.}} @article{Asa-TCS-85, title = {{An approach to the subgraph homeomorphism problem}}, author = {Tetsuo Asano}, journal = {Theoretical Computer Science}, volume = {38}, pages = {249--267}, year = {1985}, abstract = {The subgraph homeomorphism problem for a fixed pattern graph $H$ is stated as follows: given an input graph $G=(V, E)$, determine whether $G$ has a subgraph homeomorphic to $H$. The author shows that the subgraph homeomorphism problem for the fixed graph $K_3,3$ is solvable in polynomial time, where $K_3,3$ is the Thomsen graph, one of the Kuratowski graphs used to characterize planar graphs. Specifically, the author presents an $O(|V|)$-time algorithm for this problem. This problem was suspected to be NP-complete by Fortune, Hopcroft and Wyllie (1980). He also presents several pattern graphs for each of which an $O(|B|)$-time algorithm exists.}} @article{Att-CICS-83, title = {{DARC substructure search system: a new approach to chemical information}}, author = {R. Attias}, journal = {J. Chemical Information and Computer Sciences}, volume = {23}, pages = {102--108}, year = {1983}, abstract = {The efficiency of a chemical information system depends upon information parameters retained by the language used to describe compounds. Structural-based languages provide a specific approach to chemical problems. The DARC system allows a coherent approach to substructure search, structure-activity correlation, and computer-aided design by defining relationships between the notions of substructure, structure, and family of structures. The substructure search is based on the concept of fuzziness: it is expressed in terms of subgraph isomorphism between a set of fuzzy graphs and a set of graphs. The file to be searched is processed by an automat which generates multilevel fuzzy graphs corresponding to local descriptions of the defined structures. The DARC descriptions of these graphs are stored in a tree structure. The same process is applied to the fuzzy graph of a query. As a result of this approach, the user language is the natural language of the chemist: free drawing of the substructural diagram with no use of a dictionary for the search. The retrieved structures can be displayed on a graphic terminal. These principles have been applied to the full CAS Registry Structure File and have made possible, for the first time, online substructure searches on 5 million compounds (EURECAS). An automatic link to the textual data base (CA SEARCH) makes it possible to deal with both structural and textual aspects of the query.}} @inproceedings{AweBerCow-FOCS-93, title = {{Near-linear cost sequential and distributed constructions of sparse neighborhood covers}}, author = {B. Awerbuch and B. Berger and L. Cowen and D. Peleg}, booktitle = {Proc. 34th IEEE Symp. Foundations of Computer Science}, pages = {638--647}, year = {1993}, comment = {These neighborhood covers are similar to the low-treewidth covers used by Bak83 and Epp95}, abstract = {This paper introduces the first near-linear (specifically, O(E log n + n log{$^\wedge$}2 n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This automatically implies analogous improvements (from quadratic to near-linear) to all the results in the literature that rely on network decompositions, both in sequential and distributed domains, including adaptive routing schemes with O(1) stretch and memory, small edge cuts in planar graphs, sequential algorithms for dynamic approximate shortest paths with O(E) cost for edge insertion/deletion and O(1) time to answer shortest-path queries, weight and distance-preserving graph spanners with O(E) running time and space, and distributed asynchronous 'from-scratch' breadth-first-search and network synchronizer constructions with O(1) message and space overhead (down from O(n)).}} @article{AweBerCow-SJC-98, title = {{Near-linear time construction of sparse neighborhood covers}}, author = {Baruch Awerbuch and Bonnie Berger and Lenore Cowen and David Peleg}, journal = {SIAM J. Computing}, publisher = {Soc. Industrial {\&} Applied Math.}, volume = {28}, number = {1}, pages = {263--277}, year = {1998}, abstract = {This paper introduces a near-linear time sequential algorithm for constructing a sparse neighborhood cover. This implies analogous improvements (from quadratic to near-linear time) for any problem whose solution relies on network decompositions, including small edge cuts in planar graphs, approximate shortest paths, and weight- and distance-preserving graph spanners. In particular, an O(log n) approximation to the k-shortest paths problem on an n-vertex, E-edge graph is obtained that runs in O(n+E+k) time.}} @inproceedings{AweBerCow-SWAT-92, title = {{Low-diameter graph decomposition is in NC}}, author = {B. Awerbuch and B. Berger and L. Cowen and D. Peleg}, booktitle = {3rd Scand. Worksh. Algorithm Theory (SWAT)}, publisher = {Springer-Verlag Lecture Notes in Computer Science}, volume = {621}, pages = {83--93}, year = {1992}, abstract = {The authors obtain the first deterministic NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. They achieve this through derandomizing an algorithm of N. Linial and M. Saks. The authors algorithm runs in O(log{$^\wedge$}5 n) time and uses O(n{$^\wedge$}2) processors.}} @inproceedings{AwePel-FOCS-90, title = {{Sparse partitions}}, author = {B. Awerbuch and D. Peleg}, booktitle = {Proc. 31st IEEE Symp. Foundations of Computer Science}, pages = {503--513}, year = {1990}, comment = {These neighborhood covers are similar to the low-treewidth covers used by Bak83 and Epp95}, abstract = {A collection of clustering and decomposition techniques that make possible the construction of sparse and locality-preserving representations for arbitrary networks is presented. The representation method considered is based on breaking the network G(V,E) into connected regions, or clusters, thus obtaining a cover for the network, i.e. a collection of clusters that covers the entire set of vertices V. Several other graph-theoretic structures that are strongly related to covers are discussed. These include sparse spanners, tree covers of graphs and the concepts of regional matchings and diameter-based separators. All of these structures can be constructed by means of one of the clustering algorithms given, and each has proved a convenient representation for handling certain network applications.}} @inproceedings{Bab-FCT-81, title = {{Moderately exponential bound for graph isomorphism}}, author = {L{\'a}szl{\'o} Babai}, booktitle = {Proc. Int. Conf. Fundamentals of Computation Theory}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {34--50}, year = {1981}, abstract = {Presents recent major developments concerning the complexity of graph isomorphism testing. The main result is a general $exp(v^{1-c})$ bound, due to V. N. Zemlyachenko. The proof operates on the pioneering techniques of E. M. Luks which are briefly reviewed here.}} @inproceedings{BaeVal-SPIRE-00, title = {{An image similarity measure based on graph matching}}, author = {Ricardo Baeza-Yates and Gabriel Valiente}, booktitle = {Proc. 7th Int. Symp. String Processing and Information Retrieval}, publisher = {IEEE Computer Science Press}, pages = {28--38}, year = {2000}, abstract = {The problem of computing the similarity between two images is transformed to that of approximating the distance between two extended region adjacency graphs, which are extracted from the images in time and space linear in the number of pixels. Invariance to translation and rotation is thus achieved. Invariance to scaling is also achieved by taking the relative size of regions into account. Furthermore, the method provides a trade-off between pixel similarity threshold and approximation of the distance measure, which can be used to bound the error in image recognition as well as the time complexity of the computation.}} @inproceedings{Bak-FOCS-83, title = {{Approximation algorithms for NP-complete problems on planar graphs}}, author = {Brenda S. Baker}, booktitle = {Proc. 24th Symp. Foundations of Computer Science}, publisher = {Inst. Electrical {\&} Electronics Engineers}, pages = {265--273}, year = {1983}} @article{Bak-JACM-94, title = {{Approximation algorithms for NP-complete problems on planar graphs}}, author = {Brenda S. Baker}, journal = {J. Assoc. Comput. Mach.}, volume = {41}, pages = {153--180}, year = {1994}, comment = {Includes approximations for $H$-matching (finding a maximum number of disjoint subgraph isomorphs). Her scheme works by removing every $k$ levels of the graph and doing dynamic programming on the remaining pieces, an idea re-used for subgraph isomorphism in \cite{Epp-SODA-95}.}, abstract = {Describes a general technique that can be used to obtain approximation schemes for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form called $k$-outerplanar. For fixed $k$, the problems of interest are solvable optimally in linear time on $k$-outerplanar graphs by dynamic programming. For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each $k$ a linear time algorithm that produces a solution whose size is at least $k/(k+1)$ optimal. If the problem is a minimization problem, such as minimum vertex cover, it gives for each $k$ a linear time algorithm that produces a solution whose size is at most $(k+1)/k$ optimal.}} @inproceedings{BamFig-ICRA-85, title = {{Efficient new techniques for identification and 3D attitude determination of space objects from a single image}}, author = {B. Bamieh and De Figueiredo, Rui J. P.}, booktitle = {IEEE Int. Conf. Robotics and Automation}, pages = {67--72}, year = {1985}, abstract = {New algorithms are presented for rapid identification and three-dimensional (3D) attitude determination of a solid object from a single image, using a model-matching approach. The scheme allows the observed object to be partially occluded. The object, as well as the model to which it is matched, is represented by the 3D surfaces constituting their boundaries. It is assumed that these surfaces consist of flat faces, i.e. the object and the model are (not necessarily convex) polyhedra. Each is represented by an attributed graph. The nodes of the graph denotes faces on the surface, and edges indicate the adjacency of faces. Attributes on the nodes are features invariant to 3D motion made up of 2D moment invariants. With this representation the recognition problem becomes a subgraph matching problem between the image of the observed object and the stored models. An algorithm for the matching process is included. The exact attitude is obtained as a byproduct of the matching procedure.}} @article{BamFig-JRA-86, title = {{A general moment-invariants/attributed-graph method for three-dimensional object recognition from a single image}}, author = {B. Bamieh and De Figueiredo, Rui J. P.}, journal = {IEEE J. Robotics and Automation}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {RA-2}, pages = {31--41}, year = {1986}, abstract = {A consistent development of general moment invariants of affine transformations for two-dimensional image functions is presented. Based on this development, a general moment-invariants/attributed-graph method is presented for the identification of three-dimensional objects from a single observed image using a model-matching approach. The three-dimensional location and orientation parameters of the object are also obtained as a by-product of the matching procedure. The scheme presented allows the observed object to be partially occluded. For identification purposes, a three-dimensional object is represented by an attributed graph describing the geometrical structure and shape of the surface bounding the object. In such a description, two-dimensional general moment invariants of the rigid planar patches constituting the object faces are used as attributes or feature vectors which are invariant under three-dimensional motion. With this representation, the identification problem becomes a subgraph isomorphism problem between the observed image and a library model. An algorithm is presented for this matching process, and the results are illustrated by computer simulations.}} @article{BarBur-IPL-76, title = {{Subgraph isomorphism, matching relational structures and maximal cliques}}, author = {H. G. Barrow and R. M. Burstall}, journal = {Information Processing Letters}, volume = {4}, pages = {83--84}, year = {1976}, abstract = {Given two graphs $G_1$ and $G_2$ one may distinguish four problems of increasing difficulty, each a special case of the one which follows it. (i) Graph isomorphism: is $G_1$ isomorphic to $G_2$? (ii) Subgraph isomorphism: is $G_1$ isomorphic to a subgraph of $G_2$? (iii) Common subgraphs (or just maximal common ones): find the (maximal) isomorphic pairs $(H_1,H_2)$ such that $H_1$ is a subgraph of $G_1$ and $H_2$ of $G_2$. (iv) Maximal matches: find the maximal matches, where a match is a correspondence (many-many relation) between a subgraph $H_1$ of $G_1$ and a subgraph $H_2$ of $G_2$, which preserves the relation. Problem (ii) is known to be polynomial complete (4) and hence it is conjectured that no algorithm for solving it in polynomial time exists. The interest here is problems (iii) and (iv) and the authors give a method for the more general problem (iv); the method has proved to be useful in practice and is based upon the simple observation that algorithms for finding cliques can be used for this problem.}} @inproceedings{BarEve-STOC-82, title = {{On approximating a vertex cover for planar graphs}}, author = {R. Bar-Yehuda and S. Even}, booktitle = {Proc. 14th Symp. Theory of Computing}, publisher = {Assoc. Comput. Mach.}, pages = {303--309}, year = {1982}} @article{BayEis-AM-91, title = {{Graph curves}}, author = {David Bayer and D. Eisenbud}, journal = {Advances in Math.}, volume = {86}, pages = {1--40}, year = {1991}} @article{BaySimJoh-CICS-92, title = {{An algorithm for the multiple common subgraph problem}}, author = {D. M. Bayada and R. W. Simpson and A. P. Johnson and C. Laurenco}, journal = {J. Chemical Information and Computer Sciences}, volume = {32}, pages = {680--685}, year = {1992}, abstract = {The multiple largest common subgraph (MLCS) problem is presented, and a new algorithm and its implementation to solve this problem are described. The method consists of using a largest common subgraphs algorithm (LCSA) and a maximal common subgraphs algorithm (SUPLIMIT) that is a modification of LCSA. Because the largest common subgraph problem is a polynomial problem for trees, LCSA explores the spanning trees of the graphs and uses a backtracking method to be exhaustive in its search. A heuristic in LCSA gives numbers to the nodes of each graph such that nodes having a smaller number are more likely to be in a solution. LCSA, together with SUPLIMIT, is used in a series of pairwise graph comparisons to solve the MLCS problem. A preprocessing function is used to find a lower bound for the size of solutions to this problem. This improves the efficiency of the algorithm.}} @article{BenBerAga-DAM-88, title = {{Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery}}, author = {J. D. Benstock and D. J. Berndt and K. K. Agarwal}, journal = {Discrete Applied Mathematics}, volume = {19}, pages = {45--63}, year = {1988}, abstract = {Graph embedding (subgraph isomorphism) is an NP-complete problem of great theoretical and practical importance in the sciences, especially chemistry and computer science. The paper presents positive test results for techniques to speed embedding by modeling graphs with subroutines, precalculating edge tables, turning recursion into iteration, and using search-ordering heuristics. The expert system SYNCHEM2 searches for synthesis routes of organic molecules without the online guidance of a user, and the authors examine how embedding information helps to implement the central operations of SYNCHEM2: selection, application, and evaluation of chemical reactions. The authors also outline the architecture of SYNCHEM2, analyzes the computational time complexity of embedding and related problems in graph isomorphism and canonical chemical naming, and suggests topics and techniques for further research.}} @inproceedings{BenHruSte-ASU-94, title = {{Rooted graphs with types and inheritance}}, author = {M. Benes and T. Hruska and E. Stevko}, booktitle = {Proc. 20th Conf. ASU}, pages = {194--203}, year = {1994}, abstract = {Defines the concept of a rooted graph extended with types of nodes. The type system is based on inheritance, both in attributes and successors of nodes. Such graphs allow one to introduce graph rewriting systems with potentially more effective subgraph matching algorithms and with more semantics expressed with type information. The implementation of a graph using the C++ language is proposed, and a typed version of the aLean language is presented.}} @incollection{BerEpp-CEG-92, title = {{Mesh generation and optimal triangulation}}, author = {Marshall W. Bern and David Eppstein}, booktitle = {Computing in Euclidean Geometry}, publisher = {World Scientific}, editor = {F. K. Hwang and Ding-Zhu Du}, pages = {23--90}, year = {1992}, comment = {Uses a list of all triangle subgraphs in visibility graphs as a subroutine for minimum weight triangulation of polygons.}} @article{BerJohLei-Algs-90, title = {{Generalized planar matching}}, author = {F. Berman and David S. Johnson and F. T. Leighton and Peter W. Shor and L. Snyder}, journal = {J. Algorithms}, volume = {11}, pages = {153--184}, year = {1990}, abstract = {Proves that maximum planar H-matching (the problem of determining the maximum number of node-disjoint copies of the fixed graph H contained in a variable planar graph G) is NP-complete for any connected planar graph H with three or more nodes. The authors also show that perfect planar H-matching is NP-complete for any connected outerplanar graph H with three or more nodes. The results generalize and unify several special-case results proved in the literature. The techniques can also be applied to determine the complexity of several problems, including the optimal tile salvage problem from wafer-scale integration and the classic dots and boxes game. Although the authors prove that the optimal tile salvage problem and others like it are NP-complete, they also describe provably good approximation algorithms that are suitable for practical applications.}} @article{BerLawWon-Algs-87, title = {{Linear-time computation of optimal subgraphs of decomposable graphs}}, author = {Marshall W. Bern and Eugene L. Lawler and A. L. Wong}, journal = {J. Algorithms}, volume = {8}, pages = {216--235}, year = {1987}, abstract = {A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well-known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. The authors suggest a general approach for constructing linear-time algorithms in the case where the graph G is defined by certain rules of composition (as are trees, series-parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a property that is 'regular' with respect to these rules of composition (as do matchings, dominating sets, and independent sets for all the classes just mentioned). This approach is applied to obtain linear-time algorithm for computing the irredundance number of a tree, a problem for which no polynomial-time algorithm was previously known.}} @inproceedings{BerLawWon-FOCS-85, title = {{Why certain subgraph computations require only linear time}}, author = {Marshall W. Bern and Eugene L. Lawler and A. L. Wong}, booktitle = {Proc. 26th Symp. Foundations of Computer Science}, publisher = {Inst. Electrical {\&} Electronics Engineers}, pages = {117--125}, year = {1985}} @article{BeyJonMit-JACM-79, title = {{Linear algorithms for isomorphism of maximal outerplanar graphs}}, author = {T. Beyer and W. Jones and S. Mitchell}, journal = {J. Assoc. Comput. Mach.}, volume = {26}, pages = {603--610}, year = {1979}, abstract = {Two linear algorithms are presented for solving the isomorphism problem for maximal outerplanar graphs (mops). These algorithms present improvements over corresponding linear algorithms for planar graph isomorphism when applied to mops. The algorithms are based on a code for a mop G which is obtained from a unique Hamiltonian cycle in G. The first involves a string-matching automaton and the second involves the removal of vertices of degree two in layers until either an edge or triangular face remains.}} @article{BieDea-JCTB-92, title = {{On obstructions to small face covers in planar graphs}}, author = {D. Bienstock and N. Dean}, journal = {J. Combinatorial Theory, Series B}, volume = {55}, pages = {163--189}, year = {1992}, abstract = {Several algorithmic and graph-theoretic developments have focused on the problem of covering, in a planar graph, selected vertices with fewest possible faces. The paper discusses some obstructions to the existence of small face covers. If the embedding of the graph is fixed, this problem leads to variants of the Erd{\"o}s-Posa theorem (1965) on independent cycles in a graph. If the embedding of the graph is not fixed, the analysis leads to generalizations of outerplanar graphs, and an explicit upper bound is obtained on the size of the minimal excluded minors for such classes of graphs.}} @article{BieMal-EL-87, title = {{A neural network for invariant pattern recognition}}, author = {E. Bienenstock and von der Malsburg, C.}, journal = {Europhysics Letters}, volume = {4}, pages = {121--126}, year = {1987}, abstract = {The authors consider the problem of recognizing a shifted and distorted 2-dimensional shape. This task is formalized as a problem of labelled graph matching. To solve this problem, they construct an energy function similar to the one used in a previous paper (ibid., vol.3, p.1243, 1987) for solving the subgraph retrieval problem. They present a neuronal model for invariant pattern recognition, based on this solution to subgraph retrieval and graph matching.}} @article{BieRobSey-JCTB-91, title = {{Quickly excluding a forest}}, author = {D. Bienstock and Neil Robertson and Paul D. Seymour and Robin Thomas}, journal = {J. Combinatorial Theory, Series B}, volume = {52}, pages = {274--283}, year = {1991}, abstract = {The authors prove that for every forest F, every graph with no minor isomorphic to F has path-width at most |V(F)|-2.}} @article{BixWan-MPS-78, title = {{An algorithm for finding Hamiltonian circuits in certain graphs}}, author = {R. E. Bixby and D.-L. Wang}, journal = {Mathematical Programming Studies}, pages = {35--49}, year = {1978}, abstract = {A direct algorithmic procedure is described for computing Hamiltonian circuits in graphs which satisfy a condition due to Chvatal. For a graph with $p$ vertices this procedure works in $O(p^3)$ operations. It is suggested how this procedure might be used heuristically to compute long paths in general graphs.}} @article{Bod-Algs-93, title = {{On linear time minor tests with depth-first search}}, author = {Hans L. Bodlaender}, journal = {J. Algorithms}, volume = {14}, pages = {1--23}, year = {1993}, abstract = {Recent results on graph minors make it desirable to have efficient algorithms that, for a fixed set of graphs $(H_1,\ldots, H_c)$, test whether a given graph $G$ contains at least one graph $H_i$ as a minor. The author shows the following result: if at least one graph $H_i$ is a minor of a $2\times{k}$ grid graph, and at least one graph $H_i$ is a minor of a circus graph, then one can test in $O(n)$ time whether a given graph $G$ contains at least one graph $H$ in $(H_1,\ldots, H_c)$ as a minor. This result generalizes a result of M. R. Fellows and M. A. Langston (1988). The algorithm is based on depth-first search and on dynamic programming on graphs with bounded treewidth. As a corollary, it follows that the maximum leaf spanning tree problem can be solved in linear time for fixed $k$. The author also discusses that, with small modifications, an algorithm of Fellows and Langston can be modified to an algorithm that finds in $O(k! 2^k n)$ time a cycle (or path) in a given graph with length $\ge k$ if it exists.}} @article{Bod-EATCS-88, title = {{Some classes of graph with bounded treewidth}}, author = {Hans L. Bodlaender}, journal = {Bull. Eur. Assn. for Theoretical Computer Science}, volume = {36}, pages = {116--126}, month = {October}, year = {1988}} @inproceedings{Bod-STOC-93, title = {{A linear time algorithm for finding tree-decompositions of small treewidth}}, author = {Hans L. Bodlaender}, booktitle = {Proc. 25th Symp. Theory of Computing}, publisher = {Assoc. Comput. Mach.}, pages = {226--234}, year = {1993}, abstract = {In this paper, we give, for constant k, a linear time algorithm, that given a graph G=(V,E), determines whether the treewidth of G is at most k, and if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm.}} @inproceedings{Bod-WADS-89, title = {{On linear time minor tests with depth-first search}}, author = {Hans L. Bodlaender}, booktitle = {Proc. 1st Worksh. Algorithms and Data Structures}, number = {382}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {577--590}, year = {1989}} @article{BolTho-EJC-81, title = {{Graphs which contain all small graphs}}, author = {B. Bollob{\'a}s and Andrew Thomason}, journal = {Eur. J. Combinatorics}, volume = {2}, pages = {13--15}, year = {1981}, abstract = {Given a graph $H$, is there a strongly regular graph $G$ continuing $H$ as an induced subgraph? This question, posed by M. Rosenfeld, is answered here in the affirmative. In fact, given $r$, the authors look for graphs of small order $n$ which contain every graph of order $r$ as an induced subgraph. In order to abbreviate this rather clumsy description, they say that they are looking for $r$-full graphs of small order. It is shown that if $n$ is slightly greater than $2^{(r-1)/2}$, not only does there exist an $r$-full graph of order $n$ but almost every graph of order $n$ is $r$-full. They are unable to give a concrete example of an $r$-full graph of such small order. They do, however, exhibit an $r$-full graph of order $2^r$ which is rather close to being strongly regular. Finally, they display a strongly regular $r$-full graph of order roughly $r^2 2^{2r}$.}} @article{BopHal-BIT-92, title = {{Approximating Maximum Independent Sets by Excluding Subgraphs}}, author = {Ravi Boppana and Magn{\'u}s M. Halld{\'o}rsson}, journal = {BIT}, volume = {32}, pages = {180--196}, year = {1992}, abstract = {An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known to $O(n/(\log{n})^2)$. The paper also obtains the same performance guarantee for graph coloring. The results can be combined into a surprisingly strong simultaneous performance guarantee for the clique and coloring problems. The framework of subgraph-excluding algorithms is presented. The paper surveys the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and shows how almost all fit into that framework. It shows that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.}} @inproceedings{BopHal-SWAT-90, title = {{Approximating Maximum Independent Sets by Excluding Subgraphs}}, author = {Ravi Boppana and Magn{\'u}s M. Halld{\'o}rsson}, booktitle = {Proc. 2nd Scand. Worksh. Algorithm Theory}, number = {447}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {13--25}, year = {1990}} @article{BriGilLyn-PC-88, title = {{Chemical graph matching using transputer networks}}, author = {A. T. Brint and V. J. Gillet and M. F. Lynch and P. Willett and G. A. Manson and G. A. Wilson}, journal = {Parallel Computing}, volume = {8}, pages = {295--300}, year = {1988}, abstract = {Discusses the use of networks of transputers for the matching of the labelled graphs which are used to represent chemical structures in computer-based chemical information systems in particular, the implementation of a relaxation algorithm for chemical substructure searching is described. Tests with a doubly-linked chain of transputers suggest that near-linear speedups can be obtained by a partitioning of the database which is to be searched; lesser speedups are obtained with other network configurations. Current work is described involving the exploitation of an alternative level of parallelism in the relaxation algorithm and the parallel implementation of an algorithm for the identification of the maximal substructures common to a pair of chemical compounds.}} @article{BriWil-CICS-87, title = {{Algorithms for the identification of three-dimensional maximal common substructures}}, author = {A. T. Brint and P. Willett}, journal = {J. Chemical Information and Computer Sciences}, volume = {27}, pages = {152--158}, year = {1987}, abstract = {Two algorithms are described for the identification of the maximal substructures common to two (or more) three-dimensional chemical structures, where a substructure consists of a set of atoms and the associated interatomic distances. The algorithm of Crandell and Smith involves a breadth-first tree search procedure in which substructures are expanded as they are shown to be common to all of the molecules under consideration. The clique-detection algorithm involves the identification of cliques in the correspondence graph linking matching atoms and interatomic distances in pairs of structures that are being compared. The second algorithm is shown to be substantially faster in operation that the Crandell and Smith algorithm when applied to structures taken from the Cambridge Crystallographic Data Bank, and an extension to the algorithm is described that allows it to be used for the identification of the maximal substructure common to arbitrary numbers of molecules.}} @article{BroDowWil-CICS-92, title = {{A hyperstructure model for chemical structure handling: generation and atom-by-atom searching of hyperstructures}}, author = {R. D. Brown and G. M. Downs and P. Willett and P. F. Cook}, journal = {J. Chemical Information and Computer Sciences}, volume = {32}, pages = {522--531}, year = {1992}, abstract = {Discusses the representation of sets of chemical structures by hyperstructures, pseudomolecules in which areas of structural commonality are stored nonredundantly. Two methods are described for the construction of hyperstructures, and it is shown that one of these methods, the atom-assignment method, is far less demanding of computational resources than the other. Experiments with a file of 10 K structures demonstrate that the hyperstructure for a dataset requires less storage than the original set of structures; however, the difference is not large. The experiments also demonstrate that hyperstructures have at least some potential for increasing the speed of atom-by-atom searching, as compared with conventional chemical database systems.}} @article{BroTho-IEEI-88, title = {{Goal-oriented subgraph isomorphism technique for IC device recognition}}, author = {A. D. Brown and P. R. Thomas}, journal = {IEE Proceedings I (Solid-State and Electron Devices)}, volume = {135}, pages = {141--150}, year = {1988}, abstract = {Describes a programmable mask analysis system to check technology rules and extract circuits in a low cost computing environment. The mask verification language (MVL) programmer is only concerned with how a device is fabricated and not with how it is actually recognised. The system includes an optimising MVL compiler that removes redundant mask operations, and efficiency is thereby maximised by minimising the volume of mask data that must be processed.}} @article{Bud-Aut-92, title = {{On the problem of attributed relational graph matching}}, author = {A. Budin}, journal = {Automatika}, volume = {33}, pages = {151--157}, year = {1992}, abstract = {A major class of various knowledge representation methods in computer vision systems utilize graphs for the representation and the analysis of images. An important issue in such representations is the problem of graph matching or subgraph matching, i.e. the definition of a distance measure between represented objects. The paper discusses some of the different approaches to this problem and how it should be dealt with when using Petri net graphs in the knowledge representation scheme KRP.}} @article{BuiPec-SJC-92, title = {{Partitioning planar graphs}}, author = {Thang Nguyen Bui and A. Peck}, journal = {SIAM J. Computing}, publisher = {Soc. Industrial {\&} Applied Math.}, volume = {21}, pages = {203--215}, year = {1992}, abstract = {A common problem in graph theory is that of dividing the vertices of a graph into two sets of prescribed size while cutting a minimum number of edges. In the paper the problem is considered as it is restricted to the class of planar graphs. Let $G$ be a planar graph on $n$ vertices and $s\in (0,n)$ be given. An $s$-partition of $G$ is a partition of the vertex set of $G$ into sets of size $s$ and $n-s$. An optimal $s$-partition is an $s$-partition that cuts the fewest number of edges. The main result is an algorithm that finds an optimal $s$-partition in time $O(b^2 n^3 2^{4.5b})$, where $b$ is the number of edges cut by an optimal $s$-partition. In particular, by letting $s=n/2$ the immediate corollary that any planar graph with small ($O(\log{n})$) bisection width may be bisected in polynomial time is obtained. Furthermore, suppose that a planar embedding $G$ of $G$ is also given such that the embedding of each biconnected component in $G$ is at most $m$-outerplanar (such an embedding is called $m$-outerplane-separable). An algorithm for finding optimal $s$-partition of $G$ in time $O(m^2 n^3 2^{3m})$ is also given.}} @article{Bun-EATCS-83, title = {{What is the distance between graphs?}}, author = {H. Bunke}, journal = {Bull. Eur. Assn. for Theoretical Computer Science}, pages = {35--39}, year = {1983}, abstract = {In many problem domains, graphs are a powerful generalisation of strings. A prominent problem dealing with the comparison of graphs is that of finding a graph or subgraph isomorphism. The issue is made more general in this paper by allowing arbitrary graphs to be matched against each other. At the one extreme, matching is identical to finding a graph isomorphism if the graphs, the similarity of which is to be determined, are identical (i.e. isomorphic). At the other extreme, the graphs to be matched against each other may be completely dissimilar, i.e. they may not have any part in common. A generalisation of the weighted string distance is introduced. The more similar two graphs are the closer is their distance and vice versa.}} @inproceedings{BunGlaTra-GGA-90, title = {{An efficient implementation of graph grammars based on the RETE matching algorithm}}, author = {H. Bunke and T. Glauser and T.-H. Tran}, booktitle = {Proc. 4th Int. Worksh. Graph Grammars and Their Application to Computer Science}, publisher = {Springer-Verlag}, pages = {174--189}, year = {1990}, abstract = {The paper is concerned with the efficient determination of the set of productions of a graph grammar that are applicable in one rewriting step. It proposes a new algorithm that is a generalization of a similar algorithm originally developed for forward chaining production systems. The time complexity of the proposed method is not better than that of a naive solution, in the worst case. In the best case, however, a significant speedup can be achieved. Some experiments supporting the results of theoretical complexity analysis are described.}} @inproceedings{BunGlaTra-TAIA-91, title = {{Efficient matching of dynamically changing graphs}}, author = {H. Bunke and T. Glauser and T.-H. Tran}, booktitle = {Selected Papers from 7th Scandinavian Conf. Theory and Applications of Image Analysis}, publisher = {World Scientific}, pages = {110--124}, year = {1991}, abstract = {Subgraph isomorphism detection is a fundamental technique in computer vision. This paper proposes a new subgraph matching procedure that is particularly useful if the number of prototype graphs is large, and if the graph representation of the image to be interpreted is dynamically changing. The procedure is derived from the RETE-matching algorithm developed for forward chaining rule-based systems. The computational complexity of the proposed approach is not better than that of a naive, straightforward solution to the problem. In the best instance, however, a significant speedup can be achieved. Experimental results confirm the theoretical complexity analysis.}} @inproceedings{BunMes-TCBR-93, title = {{Similarity measures for structured representations}}, author = {H. Bunke and Bruno T. Messmer}, booktitle = {Selected Papers from 1st Eur. Worksh. Topics in Case-Based Reasoning}, publisher = {Springer-Verlag}, pages = {106--118}, year = {1993}, abstract = {A key concept in case-based reasoning is similarity. We propose a similarity measure for structured representations that is based on graph edit operations. We show how this similarity measure can be computed by means of state space search. Subsequently, subgraph isomorphism is considered as a special case of graph similarity and a new efficient algorithm for its detection is proposed. The new algorithm is particularly suitable if there is a large number of library cases being tested against an input graph. We also present experimental results showing the computational efficiency of the proposed approach.}} @article{BurRus-JGT-80, title = {{On the Ramsey multiplicities of graph problems and recent results}}, author = {S. A. Burr and V. Rusta}, journal = {J. Graph Theory}, volume = {4}, pages = {347--361}, year = {1980}} @article{ChaLee-TPDS-93, title = {{Fault-tolerant embedding of complete binary trees in hypercubes}}, author = {M. Y. Chan and S.-J. Lee}, journal = {Trans. Parallel and Distributed Systems}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {4}, pages = {277--288}, year = {1993}, abstract = {The focus is on the following graph-theoretic question associated with the simulation of complete binary trees by faulty hypercubes: if a certain number of nodes or links are removed from an $n$-cube, will an $(n-1)$-tree still exists as a subgraph? While the general problem of determining whether a $k$-tree, $ki\ge 1$ such that $G_i$ is isomorphic to a minor of $G_j$. J. Kruskal (1960) proved this when $G_1$, $G_2$, $\ldots$ are all trees. The authors prove a strengthening of Kruskal's result: Wagner's conjecture is true for all sequences in which $G_1$ is planar.}} @article{RobSey-GM5, title = {{Graph minors V: excluding a planar graph}}, author = {Neil Robertson and Paul D. Seymour}, journal = {J. Combinatorial Theory, Series B}, volume = {41}, pages = {92--114}, year = {1986}, abstract = {The authors prove that for every planar graph H there is a number w such that every graph with no minor isomorphic to H can be constructed from graph with at most w vertices, by piecing them together in a tree structure. This has several consequences; for example, it implies that: (i) if A is a set of graphs such that no member is isomorphic to a minor of another, and some member of A is planar, then A is finite; (ii) for every fixed planar graph H there is a polynomial time algorithm to test if an arbitrary graph has a minor isomorphic to H; (iii) there is a generalization of a theorem of Erd{\"o}s and Posa (concerning the maximum number of disjoint circuits in a graph) to planar structures other than circuits.}} @article{RobSey-GM6, title = {{Graph minors VI: disjoint paths across a disc}}, author = {Neil Robertson and Paul D. Seymour}, journal = {J. Combinatorial Theory, Series B}, volume = {41}, pages = {115--138}, year = {1986}, abstract = {Let $G$ be a graph drawn on a disc, and let the vertices of $G$ on the boundary of the disc be $s_1$, $\ldots$, $s_k$, $t_1$, $\ldots$, $t_k$ in some order. When are there $k$ vertex-disjoint paths of G joining $s_i$ and $t_i$ ($1\le i\le k$), respectively? The authors give a structural characterization and a polynomial algorithm for this problem. They also solve the same question when the disc is replaced by a cylinder.}} @article{RobSey-GM7, title = {{Graph minors VII: disjoint paths on a surface}}, author = {Neil Robertson and Paul D. Seymour}, journal = {J. Combinatorial Theory, Series B}, volume = {45}, pages = {212--254}, year = {1988}, abstract = {Let $s_1$, $t_1$, $s_2$, $t_2$, $\ldots$, $s_k$, $t_k$ be vertices of a graph G drawn in a surface $\Sigma$. When are there $k$ vertex-disjoint paths of G linking $s_i$ and $t_i$ ($1\le i\le k$)? The authors study sufficient conditions-for instance, it suffices that $G$ is connected and `uses up' the surface adequately, and all the $s_i$'s and $t_j$'s are mutually `far apart'. Their results are applied to yield a polynomially bounded algorithm to solve the problem for fixed $\Sigma$ and $k$.}} @article{RobSey-GM8, title = {{Graph Minors VIII}}, author = {Neil Robertson and Paul D. Seymour}, journal = {J. Combinatorial Theory, Series B}, volume = {48}, number = {2}, pages = {227--254}, year = {1990}} @article{RobSey-GM9, title = {{Graph minors IX: disjoint crossed paths}}, author = {Neil Robertson and Paul D. Seymour}, journal = {J. Combinatorial Theory, Series B}, volume = {49}, pages = {40--77}, year = {1990}, abstract = {Let $G$ be a graph, with a cyclic order imposed on a subset of its vertices (called `special' vertices). The authors show that either (i) modulo ($\le 3$)-separations, $G$ can be drawn in a disc with no crossings except in one `small' area, and with its special vertices on the outside in the correct order, or (ii) there is a partition of the special vertices into two `semicircles', and there is a large collection of vertex-disjoint paths of $G$ running from one semicircle to the other, such that each of these paths is either crossed by another or lies between two others.}} @inproceedings{RobSeyTho-GST-91, title = {{A survey of linkless embeddings}}, author = {Neil Robertson and Paul D. Seymour and Robin Thomas}, booktitle = {Graph Structure Theory: Proc. Joint Summer Conf. Graph Minors}, number = {147}, series = {Contemporary Mathematics}, publisher = {Amer. Math. Soc.}, pages = {125--136}, year = {1991}} @article{RobSeyTho-JCTB-94, title = {{Quickly excluding a planar graph}}, author = {Neil Robertson and Paul D. Seymour and Robin Thomas}, journal = {J. Combinatorial Theory, Series B}, volume = {62}, pages = {323--348}, year = {1994}} @incollection{RocPav-SPIE-93, title = {{New method for word recognition without segmentation}}, author = {J. Rocha and T. Pavlidis}, series = {Proc. SPIE}, publisher = {Int. Soc. for Optical Engineering}, number = {1906}, pages = {74--80}, year = {1993}, abstract = {A method for recognition of word feature graphs without previous segmentation into characters is described. In the system, each subgraph of features that matches a previously defined character prototype is recognized anywhere in the word even if it corresponds to a broken character or to a character touching another one. The characters are detected in the order defined by the matching quality. Each subgraph that is recognized is introduced as a node in a direct net that compiles different alternatives of interpretation of the features in the feature graph. A path in the net represents a consistent succession of characters in the word. The method allows the recognition of characters that overlap, or that are underlined. A final search for the optimal path under certain criteria gives the best interpretation of the word features. The character recognizer uses a flexible matching between the features and a flexible grouping of the individual features to be matched. Broken characters are recognized by looking for gaps between features that may be interpreted as part of a character. Touching characters are recognized because the matching allows non-matched adjacent features. The recognition results of this system on over 4000 printed numeral characters belonging to a USPS database and on some hand printed words confirmed the method's high robustness level.}} @inproceedings{SabAgg-TVIP-93, title = {{Hypergraph based feature matching in a sequence of range images}}, author = {B. Sabata and J. K. Aggarwal}, booktitle = {Proc. 4th Int. Worksh. Time-Varying Image Processing and Moving Object Recognition}, publisher = {Elsevier}, pages = {45--56}, year = {1993}, abstract = {The key issue in motion estimation and tracking an object over a sequence of images is establishing correspondence between the features of the object in the different images of the sequence. This paper considers the problem of establishing correspondences between surfaces in a sequence of range images. We present a novel procedure for finding correspondence and show the results on real range image sequences. A hypergraph search procedure forms the basis for the algorithm that computes the correspondence between surfaces. The solution uses geometrical and topological information derived from the scenes to direct the search procedure. Two scenes are modeled as hypergraphs and the hyperedges are matched using a sub-graph isomorphism algorithm. Further, we present a sub-hypergraph isomorphism procedure to establish the correspondences between the surface patches and demonstrate the algorithm on different types of real range image sequences. We present results that show that the algorithm is robust and performs well in presence of occlusions and incorrect segmentations.}} @article{Sim-NC-91, title = {{Constrained nets for graph matching and other quadratic assignment problems}}, author = {P. D. Simic}, journal = {Neural Computation}, volume = {3}, pages = {268--281}, year = {1991}, abstract = {Some time ago R. Durbin and D. Willshaw (1987) proposed an interesting parallel algorithm (the 'elastic net') for approximately solving some geometric optimization problems, such as the 'traveling salesman problem'. Recently it has been shown that their algorithm is related to neural networks of J. J. Hopfield and D. W. Tank (1985) and that they both can be understood as the semiclassical approximation to statistical mechanics of related physical models. The main point of the elastic net algorithm is seen to be in the way one deals with the constraints when evaluating the effective cost function (free energy in the thermodynamic analogy), and not in its geometric foundation emphasized originally by Durbin and Willshaw. As a consequence, the elastic net algorithm is a special case of the more general physically based computations and can be generalized to a large class of nongeometric problems. The author further elaborates on this observation, and generalizes the elastic net to the quadratic assignment problem. He works out in detail its special case, the graph matching problem. Simulation results on random graphs and on structured (hand-designed) graphs of moderate size (20-100 nodes) are discussed.}} @article{SitRos-PR-89, title = {{Probabilistic analysis of two stage matching}}, author = {R. Sitaraman and A. Rosenfeld}, journal = {Pattern Recognition}, volume = {22}, pages = {331--343}, year = {1989}, abstract = {Studies two stages matching procedures as applied to labelled graphs and other domains relevant to computer vision. The methods do not require that the match be exact but only that it satisfies a specified error criterion. The authors show that it is computationally more efficient to initially match a subgraph and check the rest of the graph only when this match succeeds. A probabilistic analysis of the expected cost of this procedure is given with the aim of determining the optimum subgraph size which minimies the cost. The results are extended to graph matching with geometric constraints as well as to templates.}} @inproceedings{StaDai-PDPS-90, title = {{Parallel approaches to an inherently sequential problem: depth-first search}}, author = {D. A. Stacey and L. L. Daigle}, booktitle = {Proc. ISMM Intl. Conf. Parallel and Distributed Computing, and Systems}, publisher = {ACTA Press}, pages = {246--250}, year = {1990}, abstract = {Depth-first search (DFS) is a major part of many algorithms. Unfortunately, its application in these algorithms is often inherently sequential in nature and prevents the straightforward application of parallelization techniques. This paper examines two such algorithms: the search for the largest common subgraph isomorphism between two graphs and an alpha-beta search game tree search. Parallel approaches to both problems are presented. They illustrate the utility of the partitioning of data spaces (actual or logical) as a parallelization technique.}} @article{StaWah-CAI-92, title = {{Recognition of polyhedral objects under perspective views}}, author = {T. Stahs and F. M. Wahl}, journal = {Computers and Artificial Intelligence}, volume = {11}, pages = {155--172}, year = {1992}, abstract = {It is known that recognition of polyhedral objects in single 2D images of 3D scenes can be performed advantageously by analysing cluster patterns in Hough space. The efficiency of this technique is based to a great deal on the extraction of structural and geometrical object features available under orthographic but not under perspective projection. For this reason the paper presents a method to make the recognition approach applicable for perspective views too. After discussing some basic properties of perspective Hough spaces the authors propose a method for detecting vanishing points in Hough space. They are used to reconstruct an orthographic view of the perspectively observed image by orthogonalizing cluster patterns in Hough space. Recognition is realized by matching graphs extracted from these orthogonalized patterns to model graphs by means of an attributed subgraph isomorphism detection algorithm. It is supported substantially by 3D information extracted from the perspective image by vanishing point detection. A second recognition step is introduced to identify topologically correct but geometrically inconsistent isomorphisms. Simulation results prove the method to be a practicable approach for 3D object recognition under perspective views.}} @inproceedings{Sto-ACGT-88, title = {{Tilting at windmills, or My quest for nonreconstructible graphs}}, author = {P. K. Stockmeyer}, booktitle = {Proc. 250th Anniversary Conference on Graph Theory}, number = {63}, series = {Congr. Numer.}, pages = {188--200}, year = {1988}, abstract = {The construction of several new infinite families of pairs of nonreconstructible digraphs is presented. Several sporadic examples are also constructed. The digraphs are constructed by building the orbits of the subgraph isomorphisms, acting on ordered pairs of points. All possible ways of combining the orbits are then examined, in order to produce nonreconstructible digraphs.}} @inproceedings{SugTeoMit-SMC-93, title = {{Programming Hopfield network for object recognition}}, author = {P. N. Suganthan and E. K. Teoh and D. P. Mital}, booktitle = {Proc. Int. Conf. Systems, Man and Cybernetics}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {3}, pages = {114--119}, year = {1993}, abstract = {This paper investigates the performance of the Hopfield neural network as a constraint satisfaction network for invariant pattern recognition. Although the Hopfield network is known to provide instantaneous solution to optimization problems with combinatorial complexity, in some instances the solution is invalid. In this paper, we study a number of energy function formulations and experimentally explore their merits. We also present an industrial application of Hopfield network in recognizing transparent flexible membrane printed circuits and a subgraph isomorphism of synthetic line patterns invariant of position, scale and orientation. The proposed network can correctly recognize overlapped partial line patterns and offers highly parallel implementation.}} @article{SunSki-Nw-95, title = {{Recognizing small subgraphs}}, author = {G. Sundaram and S. S. Skiena}, journal = {Networks}, volume = {25}, pages = {183--191}, year = {1995}, abstract = {Although the general problem of subgraph isomorphism is NP-complete, polynomial-time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. We present general algorithms for fixed-subgraph isomorphism which improve or unify previous results. In particular, we present an $O(nm)$ algorithm for recognizing a fixed subgraph $H$ with flower number $f$ within a graph $G$ with $n$ vertices and $m$ edges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizing $C_5$ and small even cycles $C_2k$, $k\ge 3$.}} @article{SunTsa-PR-92, title = {{A new model-based approach for industrial visual inspection}}, author = {Y.-N. Sun and C.-T. Tsai}, journal = {Pattern Recognition}, volume = {25}, pages = {1327--1336}, year = {1992}, abstract = {A novel pictorial representation called pattern attributed hypergraph (PAHG) and a new structural inspection algorithm are presented. The PAHG is used to describe the pictorial information of an input pattern, which includes attributed nodes, connectivity between nodes (intra-relations), regional primitives, and neighborhood relations between regions (inter-relations). The new structural inspection algorithm based on PAHG is proposed to match the inspected scene with the model efficiently. Consequently, the amount of matching computation is significantly reduced to roughly $1/k^3$ of the currently available method (Darwish and Jain (1988)), where $k$ is the number of partitioned regions.}} @article{Sys-TCS-82, title = {{The subgraph isomorphism problem for outerplanar graphs}}, author = {M. M. Sys{\l}o}, journal = {Theoretical Computer Science}, volume = {17}, pages = {91--97}, year = {1982}, abstract = {Deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. The author shows that SUBOUTISOM remains NP-complete even when the strongest connectivity requirements are imposed on both graphs. The same result holds for the induced subgraph isomorphism problem for outerplanar graphs except the case when both graphs are 2-connected; for such graphs the author gives a polynomial algorithm which verifies whether a 2-connected outerplanar graph is an induced subgraph of another 2-connected outerplanar graph.}} @article{TakNisSai-JACM-82, title = {{Linear-time computability of combinatorial problems on series-parallel graphs}}, author = {K. Takamizawa and T. Nishizeki and N. Saito}, journal = {J. Assoc. Comput. Mach.}, volume = {29}, pages = {623--641}, year = {1982}, abstract = {A series-parallel graph can be constructed from a certain graph by recursively applying `series' and `parallel' connections. The class of such graphs, which is a well-known model of series-parallel electrical networks, is a subclass of planar graphs. It is shown in a unified manner that there exist linear-time algorithms for many combinatorial problems if an input graph is restricted to the class of series-parallel graphs. These include (i) the decision problem with respect to a property characterised by a finite number of forbidden graphs, (ii) the minimum edge (vertex) deletion problem with respect to the same property as above, and (iii) the generalised matching problem. Consequently, the following problems, among others, prove to be linear-time computable for the class of series-parallel graphs: (1) the minimum vertex cover problem, (2) the maximum outerplanar (induced) subgraph problem, (3) the minimum feedback vertex set problem, (4) the maximum (induced) line-subgraph problem, (5) the maximum matching problem, and (6) the maximum disjoint triangle problem.}} @article{Tan-IPSJ-90, title = {{Structural distances and similarities}}, author = {E. Tanaka}, journal = {Information Processing Society of Japan}, volume = {31}, pages = {1270--1279}, year = {1990}, abstract = {Discusses graph isomorphism; string searching; subtree isomorphism; subgraph isomorphism; longest common subsequences; elastic matching; structure preserving mapping and strongly structure preserving mapping; nearest neighbour interchange; attributed relational graphs; cost functions; and structure-activity relationships.}, note = {In Japanese}} @inproceedings{TheZavSta-VCIP-89, title = {{Automatic site recognition and localisation}}, author = {P. Thevenoux and B. Zavidovique and G. Stamon}, booktitle = {Visual Communications and Image Processing IV}, number = {1199}, series = {Proc. SPIE}, publisher = {Int. Soc. for Optical Engineering}, volume = {1}, pages = {296--304}, year = {1989}, abstract = {LOAS is a model-based interpretation system designed to recognize and locate sites using a 3D model. Two concurrent sensors of different types provide two views of the same area with a different point of view. This redundancy is the important source of 3D recognition. The system is organized around two major phases: model description and 2D data segmentation versus 3D scene description. Attention is focused on using 3D information as soon as possible before the matching which is performed on a subgraph pyramid basis.}} @article{ThiBod-IPL-97, title = {{Fast partitioning $l$-apex graphs with applications to approximating maximum induced-subgraph problems}}, author = {Dimitrios M. Thilikos and Hans L. Bodlaender}, journal = {Information Processing Letters}, volume = {61}, pages = {227--232}, year = {1997}} @inproceedings{TreGin-INNC-90, title = {{Invariant object recognition by inexact subgraph matching with applications in industrial part recognition}}, author = {V. Tresp and G. Gindi}, booktitle = {Proc. Int. Neural Network Conf.}, publisher = {Kluwer}, volume = {1}, pages = {95--98}, year = {1990}, abstract = {The authors present an object recognition system consisting of a preprocessing part and a matching part. In the preprocessing step, the scene is decomposed into an assembly of sticks which are described as nodes in graphs. Nodes are connected with directed arcs if the corresponding sticks are connected in the scene. Parameters associated with an arc relate to the angle formed by the two sticks and the ratio of their lengths. In this way, the scene is described by a number of disconnected graphs which are matched against a number of stored model graphs. The matching itself is performed using a recurrent network in which the activations of neurons correspond to the certainty of a match between a stick in the scene and a stick in the model base. The recognition is independent of rotation, translation and scale, and insensitive to perspective or other distortions. The system was tested in the recognition of industrial parts. Scenes of varying image quality consisted of single or multiple objects and also including overlapping pieces. A systematic performance test highlights strong and weak points of this approach.}} @article{TriKas-PAMI-94, title = {{Geometric reasoning for extraction of manufacturing features in iso-oriented polyhedrons}}, author = {S. N. Trika and R. L. Kashyap}, journal = {Trans. Pattern Analysis and Machine Intelligence}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {16}, pages = {1087--1100}, year = {1994}, abstract = {This paper investigates the extraction of machining features from boundary descriptions of iso-oriented (having no inclined faces) polyhedrons. We prove that manufacturing the features proposed by our feature extractor results exactly in the desired part-in this respect, the approach is both sound and complete. Our method uses the adjacency information between faces to derive the features. This keeps the determination of isolated features in a part straightforward. However, interaction of features creates difficulties since the adjacency information between some faces is lost. We derive this lost information by considering faces that when extended intersect other faces to form concave edges. The derived face adjacencies are termed virtual links. Augmenting the virtual links to the cavity graph of the object leads to its feature graph, and subgraph matching of primitive graphs in this graph results in feature hypotheses. A feature hypothesis is considered valid if the volume corresponding to it is not shared with the part in question; therefore, we verify the feature hypotheses by checking the regularized intersection of the feature volume and the part. Thus, feature verification employs a constructive solid geometry approach. We have implemented a prototype of the system in the Smalltalk-80 environment.}} @article{TruSou-MOR-79, title = {{Minimal forbidden subgraphs of unimodular multicommodity networks}}, author = {K. Truemper and Y. Soun}, journal = {Mathematics of Operations Research}, volume = {4}, pages = {379--389}, year = {1979}, abstract = {An integral matrix with independent columns is called unimodular if the greatest common divisor of the determinants of its maximum-rank square submatrices is one. An integral matrix $A$ (not necessarily having independent columns) is defined to be unimodular if every basis of $A$ has that property. It is known that this is so if and only if the extreme points of the set of nonnegative vectors $x$ satisfying $Ax=b$ are integral for all integral vectors $b$. The constraint matrix of a $k$-commodity network flow problem is shown to be unimodular if and only if the associated (undirected) graph does not have a subgraph homeomorphic to the following graphs: (i) the complete graph on four nodes, and if $k\le 3$, (ii) a cycle with three additional edges, each a duplicate of a different edge of the cycle, having no node with degree 2 (these graphs have from three to six nodes).}} @article{TsaFu-SMC-83, title = {{Subgraph error-correcting isomorphisms for syntactic pattern recognition}}, author = {W.-H. Tsai and K.-S. Fu}, journal = {Trans. Systems, Man and Cybernetics}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {SMC-13}, pages = {48--62}, year = {1983}, abstract = {The structure-preserved error-correcting graph isomorphism proposed by Tsai and Fu (1979) for matching patterns represented by attributed relational graphs is extended to the case of subgraphs. The resulting subgraph error-correcting isomorphism, which includes the structure-preserved error-correcting graph isomorphism as a special case, is useful for recognizing partially viewed or structurally distorted patterns. After formulating a subgraph error-correcting isomorphism as a state-space tree-search problem, heuristic information useful for speeding up the search is suggested and an ordered-search algorithm is proposed for finding an optimal subgraph error-correcting isomorphism.}} @inproceedings{Tsi-ISPRS-94, title = {{A graph-theoretical approach for multiple feature matching and its application on digital point transfer}}, author = {V. Tsingas}, booktitle = {Proc. ISPRS Commission III Symp. Spatial Information from Digital Photogrammetry and Computer Vision}, number = {2357}, series = {Proc. SPIE}, publisher = {Int. Soc. for Optical Engineering}, volume = {2}, pages = {865--871}, year = {1994}, abstract = {Digital photogrammetry allows the simultaneous use of multiple (more than two) overlapping images. Multiple image matching techniques improve the reliability and the precision of digital point determination. This paper reports on the development of a method for multiple feature matching and its application on the automatic point transfer in the aerial triangulation. The determination of corresponding points is modeled as a graph-theoretical problem. To solve this problem a special search algorithm was developed based on the methods of binary programming. Furthermore, a strategy was developed for the fully automatic use of the method in the digital point transfer. Operational aspects and empirical results of the practical use in conventional aerial triangulation with digitized photographs and data of three-line CCD camera are represented.}} @article{Tur-DAM-84, title = {{On the succinct representation of graphs}}, author = {G{\"y}orgy Tur{\'a}n}, journal = {Discrete Applied Mathematics}, volume = {8}, number = {3}, pages = {289--294}, year = {1984}} @article{Ull-JACM-76, title = {{An algorithm for subgraph isomorphism}}, author = {J. R. Ullmann}, journal = {J. Assoc. Comput. Mach.}, volume = {23}, pages = {31--42}, year = {1976}, abstract = {Subgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess the time actually taken by the new algorithm, subgraph isomorphism, clique detection, graph isomorphism, and directed graph isomorphism experiments have been carried out with random and with various nonrandom graphs. A parallel asynchronous logic-in-memory implementation of a vital part of the algorithm is also described, although this hardware has not actually been built. The hardware implementation would allow very rapid determination of isomorphism.}, review = {MR-58-13907}} @article{MR-58-13907, reviews = {Ull-JACM-76}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{An algorithm for subgraph isomorphism}}, volume = {58}, number = {{\#}13907}} @inproceedings{Ull-PRAI-76, title = {{Pattern recognition using degenerate reference data}}, author = {J. R. Ullmann}, booktitle = {Proc. Joint Worksh. Pattern Recognition and Artificial Intelligence}, publisher = {Inst. Electrical {\&} Electronics Engineers}, pages = {23}, year = {1976}, abstract = {Abstract only given substantially as follows: To reduce the total amount of computation recognition is achieved by using just one elaborate computation for each recognition class, instead of a separate computation for each separate specimen in each recognition class. The basic idea is to take the union of the representative graphs of all specimens in a given class, and determine subgraph isomorphism between an unknown pattern and this union. This idea has been applied in a watered-down form to hand-printed numeral recognition; and the paper starts by explaining why relational techniques may eventually be of practical use in character recognition.}} @article{Ume-BEL-86, title = {{Metrics for comparing structural descriptions}}, author = {S. Umeyama}, journal = {Bull. Electrotechnical Laboratory}, volume = {50}, pages = {702--712}, year = {1986}, abstract = {The problem to define metrical structural distances over a set of multiple-attributed directed graphs (MADGs) is considered. A motion of structural difference matrix between two MADGs is introduced, and a new structural distance is defined by assigning a non-negative value to the matrix. A necessary and sufficient condition for the defined structural distance to be a metric can be provided when the assigning function is a natural one, i.e. when it is monotonic and has the permutation invariant property. Various metrical structural distances based on this definition and their simple interpretations are also given.}} @article{Ume-IECEJ-87, title = {{Weighted graph matching algorithms using eigen-decomposition approach}}, author = {S. Umeyama}, journal = {Trans. Inst. Electronics and Communication Engineers of Japan E}, volume = {E70}, pages = {809--816}, year = {1987}, abstract = {Discusses the approximate solution to the weighted graph matching problem (WGMP) both for undirected and directed graphs. WGMP is the problem of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method employs an analytic approach using the eigen-decomposition of the adjacency matrix (in the case of undirected matching problem) or the singular value decomposition of the incidence matrix (in the case of directed graph matching problem) of a given graph. A technique for reducing the execution time to search for the solution is given. Simulation experiments are also given to evaluate the performance of the proposed method.}} @article{Ume-PAMI-88, title = {{An Eigendecomposition Approach to Weighted Graph Matching Problems}}, author = {S. Umeyama}, journal = {Trans. Pattern Analysis and Machine Intelligence}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {10}, pages = {695--703}, year = {1988}, abstract = {An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs. The weighted-graph-matching problem is that of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method uses an analytic instead of a combinatorial or iterative approach to the optimum matching problem. Using the eigendecompositions of the adjacency matrices (in the case of the undirected-graph-matching problem) or Hermitian matrices derived from the adjacency matrices (in the case of the directed-graph-matching problem), a matching close to the optimum can be found efficiently when the graphs are sufficiently close to each other. Simulation results are given to evaluate the performance of the proposed method.}} @inproceedings{ValMar-SAWSP-97, title = {{An algorithm for graph pattern-matching}}, author = {Gabriel Valiente and Conrado Mart{\'\i}nez}, booktitle = {Proc. 4th South Amer. Worksh. String Processing}, number = {8}, series = {International Informatics Ser.}, publisher = {Carleton University Press}, pages = {180--197}, year = {1997}, url = {http://www.lsi.upc.es/~valiente/abs-wsp-1997.pdf}, abstract = {Graph pattern-matching is a generalization of string matching and two-dimensional pattern-matching that offers a natural framework for the study of matching problems upon multi-dimensional structures. We present in this paper an algorithm for pattern-matching on arbitrary graphs that is based on reducing the problem of finding a homomorphic image of a pattern graph in a target graph, to that of finding homomorphic images of every connected component of the pattern in the target. For every connected component, the algorithm performs a combinatorial search bounded by a pruning operator. The algorithm can be applied to directed graphs as well as to undirected graphs, and it can also be specialized to find isomorphic images only.}} @article{Ver-IPL-92, title = {{Strings, trees, and patterns}}, author = {R. M. Verma}, journal = {Information Processing Letters}, volume = {41}, pages = {157--161}, year = {1992}, abstract = {The author studies subtree isomorphism and its relationships with some important symbolic problems. Recently, a linear time algorithm for ordered subtree isomorphism was given by Makinen \cite{Mak-IPL-91}. The author notes that a subtree of a rooted tree $T$, in Makinen's paper, refers to the tree rooted at any vertex in $T$. He considers ordered subtree isomorphism when a broader definition of subtree is used, namely, a subtree of $T$ is any connected subgraph, including $v$, of the tree rooted at any vertex $v$ in $T$. He gives some evidence to show that a linear time algorithm for this problem is unlikely. He also gives an almost linear time reduction from the important problem of pattern matching to ordered subtree isomorphism. Finally, he presents simpler linear time algorithms for ordered and unordered subtree isomorphism (with the more restrictive definition of subtree).}} @article{VerRey-SJC-89, title = {{An analysis of a good algorithm for the subtree problem, corrected}}, author = {R. M. Verma and S. W. Reyner}, journal = {SIAM J. Computing}, publisher = {Soc. Industrial {\&} Applied Math.}, volume = {18}, pages = {906--908}, year = {1989}, abstract = {It is shown that the proof of the main result in Reyner's paper, similarly titled, (see ibid., vol.6, p.730-2, 1977) is incorrect. Interestingly, by combining a simple modification of the algorithm with tighter analysis, one can obtain the original result with a minor improvement.}} @article{Ves-GC-91, title = {{Graphs with two isomorphism classes of spanning unicyclic subgraphs}}, author = {P. D. Vestergaard}, journal = {Graphs and Combinatorics}, volume = {7}, pages = {197--204}, year = {1991}, abstract = {The graphs whose spanning unicyclic subgraphs partition into exactly two isomorphism classes are characterized. This work is a continuation of the author's previous work (see Discrete Math., vol.70, p.103-8 (1988)) where graphs with one isomorphism class of spanning unicyclic graphs are characterized. The analogous question for spanning trees was posed by K. Wagner (1970) and graphs with one isomorphism class of spanning trees and graphs with two isomorphism classes of spanning trees are characterized in the literature.}} @article{WagCor-DAM-93, title = {{On the complexity of the embedding problem for hypercube related graphs}}, author = {A. Wagner and D. G. Corneil}, journal = {Discrete Applied Mathematics}, volume = {43}, pages = {75--95}, year = {1993}, abstract = {The n-dimensional hypercube is the graph with $2^n$ nodes labelled 0,1, $\ldots$, $2^n-1$ and an edge joining two nodes whenever their binary representation differs in a single coordinate. The problem of deciding whether a given graph is a subgraph of an $n$-dimensional cube has recently been shown to be NP-complete. The authors illustrate a reduction technique used to obtain NP-completeness results for a variety of hypercube related graphs. They consider the subgraph isomorphism problem on two related families of graphs, the dilation two hypercubes and generalized hypercubes. They show that the embedding problem for both of these families is NP-complete.}} @inproceedings{Wah-ICPR-88, title = {{Analysing Hough nets for recognition of polyhedra-like objects}}, author = {F. M. Wahl}, booktitle = {Proc. 9th Int. Conf. Pattern Recognition}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {1}, pages = {550--554}, year = {1988}, abstract = {It is shown how structural information from Hough space representations of 2-D images from 3-D scenes can be derived and used to match polyhedra-like objects topologically to 3-D wire-frame models. The matching is performed by an attributed subgraph isomorphism detection algorithm. A subsequent algorithm match can be used to verify the topological match, yielding simultaneously pose information. Simulation results show the method to be a practicable approach for 3-D object recognition.}} @article{WalBur-IS-77, title = {{Efficient algorithms for $(3,1)$ graphs}}, author = {A. M. Walsh and W. A. Burkhard}, journal = {Information Sciences}, volume = {13}, pages = {1--10}, year = {1977}, abstract = {In this paper the authors define a class of graphs which are referred to as $(3,1)$ graphs. A graph is a member of this class if it has the property that within each set of three vertices there is at least one edge. They derive a lower bound for the size of a maximum clique in a $(3,1)$ graph as well as an upper bound for the size of a minimum clique covering. In addition, it is shown that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected $(3,1)$ graph and an $n^4$-algorithm for finding a minimum coloring in a $(3,1)$ graph.}} @article{WalCol-Nw-83, title = {{Steiner trees, partial 2-trees, and minimum IFI networks}}, author = {J. A. Wald and C. J. Colbourn}, journal = {Networks}, volume = {13}, pages = {159--167}, year = {1983}, abstract = {Minimum isolated failure immune networks are shown to be 2-trees. Further, subgraphs of 2-trees are shown to be exactly those graphs which contain no subgraph homeomorphic to the four-vertex complete graph. Together, these two characterizations yield a linear time algorithm for adding lines to a network to produce a minimum isolated failure immune network, whenever this is possible. This same algorithm, in conjunction with a linear time Steiner tree algorithm for 2-trees, yields a linear time Steiner tree algorithm for partial 2-trees. This contrasts with the known NP-completeness of the Steiner tree problem for planar graphs.}} @inproceedings{WanFanLiu-ICEC-95, title = {{Adaptive optimization for solving a class of subgraph isomorphism problems}}, author = {Y.-K. Wang and K.-C. Fan and C.-W. Liu and J.-T. Horng}, booktitle = {Proc. Int. Conf. Evolutionary Computation}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {1}, pages = {44--49}, year = {1995}, abstract = {In this paper, genetic algorithms are applied to solve the error-correcting subgraph isomorphism (ECSI) problems. The error-correcting subgraph isomorphism problems are first formulated as permutation searching problems. Two ECSI algorithms are devised. The first algorithm implements pure genetic algorithms with permutation representation. The second is a hybrid algorithm that amalgamates assignment algorithms and a local search strategy to improve convergence speed. From experiments, the second algorithm shows better performance than the first one and also reveals that the approach is superior to the traditional tree search approach.}} @inproceedings{WanLi-ICPR-88, title = {{Double subgraph isomorphism method for matching LSI chip images}}, author = {J.-R. Wang and J.-G. Li}, booktitle = {Proc. 9th Int. Conf. Pattern Recognition}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {2}, pages = {945--947}, year = {1988}, abstract = {The corresponding relations between two nodes isomorphically matched are searched from the region adjacency graph of segmented chip images. Heuristic information is extracted to improve the searching efficiency in the isomorphism matching. Special criteria of region similarity measure and matching figure of surrounding string are used to select starting nodes of isomorphism matching.}} @article{WatEndMiy-CADICS-83, title = {{A new automatic logic interconnection verification system for VLSI design}}, author = {T. Watanabe and M. Endo and N. Miyahara}, journal = {Trans. Computer-Aided Design of Integrated Circuits and Systems}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {CAD-2}, pages = {70--82}, year = {1983}, abstract = {A new VLSI checking program, LIVES (Logic Interconnection VErification System), has been developed. It can perform the check even when there are no identification marks on each logic gate in layout level description data. This feature is realised by employing new algorithms based on graph theory. In the verification procedure, LIVES adopts graph isomorphism, which uses the new partitioning methods for vertices, especially tailored for the logic diagram. In the error detection procedure, a graph is divided into subgraphs, based on a new concept, 'route-subgraph', and tests for graph isomorphism between subgraphs are performed. These algorithms enable precise and rapid search for any error points in the VLSI design. These new algorithms have been implemented and examined for practical feasibility. Experimental results have ensured that this program can detect errors in the VLSI layout patterns very quickly and precisely.}} @inproceedings{Wel-GST-91, title = {{Knots and braids: some algorithmic questions}}, author = {D. J. A. Welsh}, booktitle = {Graph Structure Theory: Proc. Joint Summer Conf. Graph Minors}, number = {147}, series = {Contemporary Mathematics}, publisher = {Amer. Math. Soc.}, pages = {109--124}, year = {1991}} @article{Wil-CICS-85, title = {{An algorithm for chemical superstructure searching}}, author = {P. Willett}, journal = {J. Chemical Information and Computer Sciences}, volume = {25}, pages = {114--116}, year = {1985}, abstract = {Chemical superstructure searching involves the identification of those molecules that are contained within a given query structure. This paper presents an algorithm for carrying out such searches that may involve fewer accesses to backing storage than a previously described algorithm.}} @article{Wil-JISPP-89, title = {{Textual and chemical information processing using parallel computer hardware}}, author = {P. Willett}, journal = {J. Information Science, Principles {\&} Practice}, volume = {15}, pages = {223--236}, year = {1989}, abstract = {A discussion is given on the use of parallel computer hardware to increase the efficiency of processing in databases of text and chemical structures. After a general introduction to parallelism, two types of parallel computer are described: the ICL Distributed Array Processor and the INMOS Transputer. Experimental results are presented of the use of the DAP for cluster analysis, of the transputer for chemical substructure and maximal common substructure searching and of both machines for text retrieval.}} @inproceedings{Wil-OIM-85, title = {{Ranked output searching in textual and structural databases}}, author = {P. Willett}, booktitle = {Proc. 9th Int. Online Information Meeting, London}, publisher = {Learned Information}, address = {Oxford, UK}, pages = {343--353}, year = {1985}, abstract = {The author discusses the use of best match search techniques in the design of retrieval systems for chemical and textual databases. The first system is an operational implementation of some of the ideas that have come out of information retrieval research over the last 10-15 years, and illustrates the use of automatic query formulation, ranked output searching and relevance feedback. The second system permits the use of ranking techniques in the structure and substructure search components of conventional chemical structure handling systems. It is suggested that such techniques may become of increasing importance over the next few years with the move to end-user searching of machine-readable databases.}} @inproceedings{Wil-OIM-90, title = {{Processing of three-dimensional chemical structure information using graph-theoretic techniques}}, author = {P. Willett}, booktitle = {Proc. 14th International Online Information Mtg.}, publisher = {Learned Information}, editor = {D. I. Raitt}, address = {Oxford, UK}, pages = {115--127}, year = {1990}, abstract = {Summarises the results to date of an ongoing programme of research at the University of Sheffield to develop efficient computational procedures for the processing of databases of 3-D chemical structures. The work has involved the use of graph-like data structures and isomorphism algorithms analogous to those used for the storage and retrieval of 2-D molecules in conventional chemical information systems. The techniques have been used to provide novel means of access to the 3-D structures in the Cambridge Structural Database and in the Protein Data Bank.}} @article{WilWilRed-CICS-91, title = {{Atom-by-atom searching using massive parallelism, implementation of the Ullmann subgraph isomorphism algorithm on the Distributed Array Processor}}, author = {P. Willett and T. Wilson and S. F. Reddaway}, journal = {J. Chemical Information and Computer Sciences}, volume = {31}, pages = {225--233}, year = {1991}, abstract = {The AMT Distributed Array Processor (DAP) is a massively parallel SIMD processor array that contains thousands of processing elements. This paper describes the implementation of atom-by-atom searching on the DAP using Ullmann's subgraph isomorphism algorithm. Two alternative algorithms are discussed. The first of these allows rapid processing of a single structure, the adjacency matrix of which is distributed across the array of processing elements. The second is much slower in execution for a single molecule but allows very large numbers of structures to be searched in parallel. With current codes, the first algorithm is faster and out-performs a large mainframe; however, developments of the second algorithm are expected to make this the faster. Combined algorithms are also described that utilize both approaches.}} @article{WilWinBaw-CICS-86a, title = {{Implementation of nonhierarchic cluster analysis methods in chemical information systems: selection of compounds for biological testing and clustering of substructure search output}}, author = {P. Willett and V. Winterman and D. Bawden}, journal = {J. Chemical Information and Computer Sciences}, volume = {26}, pages = {109--118}, year = {1986}, abstract = {The use of cluster analysis techniques with machine-readable files of chemical compounds characterized by substructural fragments is reported. The first part of the paper describes a comparative evaluation of several nonhierarchic clustering methods, the evaluation involving simulated property prediction experiments using 14 small sets of compounds for which associated physical, chemical, or biological property data are available. The experiments suggest that one particular nonhierarchic clustering method, that due to Jarvis and Patrick, performs consistently better than the other methods that were tested. The second and third parts of the paper consider the use of the Jarvis-Patrick method for clustering data sets of many hundreds or thousands of chemical compounds, typical of the types of structure encountered in the chemical information systems of pharmaceutical research organizations. The first application considered is the selection of trial compounds for activity testing in biological screens, thus providing a more systematic method of compound selection than is used in current empirical screening systems. The second application is the clustering of the molecules retrieved by chemical substructure search systems so as to permit rapid identification of the main structural classes present in the search output.}} @article{WilWinBaw-CICS-86b, title = {{Implementation of nearest-neighbour searching in an online chemical structure search system}}, author = {P. Willett and V. Winterman and D. Bawden}, journal = {J. Chemical Information and Computer Sciences}, volume = {26}, pages = {36--41}, year = {1986}, abstract = {Discusses the provision of nearest-neighbour searching facilities as an adjunct to the retrieval mechanism of conventional chemical search systems. The facilities are based upon the calculation of a measure of intermolecular structural similarity between a query compound and the molecules in a machine-readable structure file. Examples are presented of the use of nearest-neighbor searching to rank output from substructure searches and to provide a means for carrying out browsing searches in structure files.}} @article{WipRog-CICS-84, title = {{Rapid subgraph search using parallelism}}, author = {W. T. Wipke and D. Rogers}, journal = {J. Chemical Information and Computer Sciences}, volume = {24}, pages = {255--262}, year = {1984}, abstract = {A new parallel processing algorithm is reported for subgraph matching. Parallelism is achieved for the first time within the process of node-by-node matching of two individual graphs. A SIMULA program is described for simulating this parallel subgraph search algorithm. Simulation results from a series of chemical substructure search problems show an average utilization of 84{\%} on a 25-processor machine and up to a 24-fold speed enhancement over a single processor. Potential applications include starting material selections for synthesis as well as general substructure search problems.}} @article{Won-PR-92, title = {{Model matching in robot vision by subgraph isomorphism}}, author = {E. K. Wong}, journal = {Pattern Recognition}, volume = {25}, pages = {287--303}, year = {1992}, abstract = {Describes a systematic method for three-dimensional (3D) model matching in robot vision by using subgraph matching techniques. 3D objects are modeled as attributed graphs, called model graphs, where the nodes correspond to object vertices and the branches correspond to object edges. The 2D projections of a 3D object are modeled as subgraph isomorphisms of the object's model graph. Recognition is done by searching whether a 2D projection graph, constructed from the 2D projection of a 3D object, is a subgraph isomorphism of the object's model graph.}} @inproceedings{WonAki-SMC-83, title = {{An algorithm for the largest common subgraph isomorphism using the implicit net}}, author = {A. K. C. Wong and F. A. Akinniyi}, booktitle = {Proc. Int. Conf. Systems, Man and Cybernetics}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {1}, pages = {197--201}, year = {1983}, abstract = {An algorithm is presented for detecting the largest common subgraph isomorphism for pairs of nonisomorphic graphs (or subgraphs). This algorithm entails a branch-and-bound search procedure over the projections of the product (called the net) of the two graphs. The objective is to detect a feasible subnet (i.e. a subgraph of the net) that preserves the largest number of incidence relations between the two graphs.}} @inproceedings{WonFu-CVRC-84, title = {{A graph-theoretic approach to model matching in computer vision}}, author = {E. K. Wong and K. S. Fu}, booktitle = {Proc. Worksh. Computer Vision: Representation and Control}, publisher = {Inst. Electrical {\&} Electronics Engineers}, pages = {106--111}, year = {1984}, abstract = {A new technique for modeling and recognition of 3-D objects is described. 3-D objects are modeled as graphs where the nodes correspond to object vertices and the branches correspond to object edges. Allowable junction types at each object vertex are assigned as the property at the corresponding node of the model graph. Allowable junction type combinations of the neighboring vertices at a given vertex are established as constraints required at the corresponding node of the model graph. The 2-D projections of an object are modeled as subgraph isomorphisms of the model graph. Recognition is by searching if a 2-D projection graph is a subgraph isomorphism of the model graphs, and each node in the projection graph also satisfies the constraints at the node of the model graph matched.}} @inproceedings{WonLi-MBV-92, title = {{Visual transformation of a 3-D object in attribute hypergraph representation}}, author = {A. K. C. Wong and C. W. Li}, booktitle = {Model-Based Vision}, number = {1827}, series = {Proc. SPIE}, publisher = {Int. Soc. for Optical Engineering}, pages = {29--40}, year = {1992}, abstract = {The authors propose a recognition method which enables a model driven vision system to recognize a 3-D object with a single view using visual transformation. The term visual transformation means geometrical transformation (rotation, translation, and magnification) and projection. When a 3-D object is represented by an attributed hypergraph (AHG) G, any single view of the object can also be expressed by an AHG say g. The recognition process involves establishing a matching between G and g. If the attributes are not considered, g is a subgraph of G. The attributes of g can be converted from those of G by a visual transformation. The objective of this research is to study the transformations of these attributes and determine if there is a possible visual transformation between the given attributes. As application, one can determine the monomorphism between the AHG of the model of an object and the AHG of a single view of the object.}} @inproceedings{WonLu-SMC-83, title = {{Representation of 3-D objects by attributed hypergraphs for computer vision}}, author = {A. K. C. Wong and S. W. Lu}, booktitle = {Proc. Int. Conf. Systems, Man and Cybernetics}, publisher = {Inst. Electrical {\&} Electronics Engineers}, volume = {1}, pages = {49--53}, year = {1983}, abstract = {A system is proposed in which a structured light source is used to obtain the surface orientation of a 3-D object. To identify the faces of the object, a segmentation scheme is used. On the basis of this information, the 3-D object is represented by an attributed graph. After a spatial transformation, the geometric features on each face of the object are obtained. An attributed subgraph, known as an elementary attributed graph, can be constructed to represent each face. For simple models such as cuboids, pyramids, and cylinders represented by attributed graphs, complicated models can be represented as hypergraphs, in which each hypervertex consists of an attributed graph representing a simple model and each hyperarc represents the set of arcs connecting a pair of these graphs. The recognition of a candidate object as one of the models is a procedure of finding a graph monomorphism or a subgraph isomorphism between the attributed hypergraph of the candidate object and that of a model in the database.}} @inproceedings{WonYan-PDCS-90, title = {{Distributed computing of graph optimal isomorphism}}, author = {A. K. C. Wong and F. Yang}, booktitle = {Proc. ISMM Intl. Conf. Parallel and Distributed Computing, and Systems}, publisher = {ACTA Press}, pages = {261--264}, year = {1990}, abstract = {Presents an iterative algorithm for finding graph optimal isomorphism with distributed implementations on a computer network. Results show that this algorithm can achieve acceptable solutions for high order graph optimal isomorphism effectively. It can also be modified for subgraph optimal isomorphism.}} @inproceedings{WuRos-GGACS-73, title = {{Cellular graph automata}}, author = {A. Wu and A. Rosenfeld}, booktitle = {Int. Worksh. Graph-grammars and their application to computer science and biology}, number = {73}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {464--475}, year = {1978}, abstract = {Labelled graphs of bounded degree, with numbers assigned to the arcs at each node, are called d-graphs. A class of generalized automata, called cellular d-graph automata, in which the intercell connections define a d-graph, is introduced. It can be shown that a cellular d-graph automaton can measure various properties of its underlying graph, can detect graph or subgraph isomorphism, and can recognize various basic types of graphs. Most of these tasks can be performed in time proportional to the diameter of a given graph. Closure properties of d-graph languages are also briefly discussed.}} @article{WuRos-IC-75, title = {{Cellular graph automata II: graph and subgraph isomorphism, graph structure recognition}}, author = {A. Wu and A. Rosenfeld}, journal = {Information and Control}, volume = {42}, pages = {330--353}, year = {1975}, abstract = {For pt.I see ibid., vol.42, no.23, p.305-29 (1979). This paper deals with cellular automata in which the intercell connections define a graph of bounded degree. It discusses acceptance tasks that involve the detection of graph or subgraph isomorphism in time proportional to the diameter of the given graph. In some of the algorithms, special assumptions are made about the 'homogeneity' of the graph; these assumptions hold for many important classes of graphs, including trees and arrays. The paper also examines types of graph structures that can be recognized by these automata. Diameter-time algorithms are presented for the recognition of cycles, strings, trees, cliques, rectangular and square arrays, Eulerian graphs, bipartite and complete bipartite graphs, stars, and wheels. The recognition of planar graphs is also discussed.}} @article{XuZha-CJC-90, title = {{From subgraph to hypergraph, a new algorithm for generating molecular structures}}, author = {Xu{ }Jun and Maosen Zhang}, journal = {Chinese J. Computers}, volume = {13}, pages = {671--678}, year = {1990}, abstract = {A new algorithm for generating molecular structures is presented. The algorithm takes subgraph as root node of structural tree and generates hypergraphs with the information of graph isomorphism and homomorphism and the chemical and spectrum constraints to avoid duplications and the development of hopeless branches. It decreases the redundancy and solves the problem of 'combinational explosion' to some extent.}, note = {In Chinese}} @article{YehKamNna-JDM-93, title = {{CAD-based automatic object recognition}}, author = {S. Yeh and M. Kamran and B. O. Nnaji}, journal = {J. Design and Manufacturing}, volume = {3}, pages = {57--73}, year = {1993}, abstract = {Research has shown that a system that possesses the capacity to reason about geometric properties of objects is an invaluable tool for overcoming many of the obstacles which prevent the integration of current CAD/CAM systems. In this paper, a genuine object-recognition process is proposed. To facilitate the recognition process, a unique boundary representation scheme is developed based on the study of geometric data preparation. By using graph theory and AI search techniques, the recognition process can be used to realize that two objects are identical or similar.}} @inproceedings{YusZwi-ICALP-94, title = {{Finding even cycles even faster}}, author = {R. Yuster and U. Zwick}, booktitle = {Proc. 21st Int. Coll. Automata Languages and Programming}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, pages = {532--543}, year = {1994}, abstract = {We describe efficient algorithms for finding even cycles in undirected graphs. The main results are the following: for every $k\ge 2$, we can, in $O(V^2)$ time, decide whether an undirected graph $G=(V,E)$ contains a simple cycle of length $2k$ and output such a cycle if it does; and we can, again in $O(V^2)$ time, find a shortest even cycle in an undirected graph $G=(V,E)$.}} @article{ZhaMinIke-JIP-92, title = {{An efficient algorithm for point pattern matching using ordered lists}}, author = {H. Zhang and M. Minoh and K. Ikeda}, journal = {J. Information Processing}, volume = {15}, pages = {108--115}, year = {1992}, abstract = {Matching two-dimensional point patterns is an important problem in the field of pattern recognition and computer vision. Mathematically, it is a graph or subgraph isomorphism problem, and belongs to the class of NP problems. An efficient algorithm is needed for practical applications. The paper presents an approach for matching point patterns by using ordered lists. The measure of matching error is defined, and a method of searching for pairing points is then discussed. The algorithm uses ordered lists to limit the range searched for pairing points, and avoids exhaustive combination of points. Experimental results show the effectiveness of the proposed algorithm. Several problems that occur in certain applications are analyzed at the end of the paper.}} @article{ZhuWuYua-CJA-93, title = {{Qualitative recognition of 3D objects from range image}}, author = {Zhuang{ }Qing and Li-De Wu and Yuan{ }Mei}, journal = {Chinese J. Automation}, volume = {5}, pages = {39--46}, year = {1993}, abstract = {In this paper, a new 3D object qualitative representation called a qualitative depth graph is presented. This symbolic representation can effectively separate occluded objects without any model guidance. Then the identification can be turned into a graph or subgraph isomorphism. A recursive scheme integrating 'purifying' with 'searching' is proposed to determine the isomorphism. Several experiments demonstrated the effectiveness and stability of the algorithm}} @misc{cs.DS/9911003, title = {{Subgraph isomorphism in planar graphs and related problems}}, author = {David Eppstein}, eprint = {cs.DS/9911003}, howpublished = {ACM Computing Research Repository}, month = {November}, year = {1999}} @misc{math.CO/9907126, title = {{Diameter and treewidth in minor-closed graph families}}, author = {David Eppstein}, eprint = {math.CO/9907126}}