% 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}}