% 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, $k