Narrow Results

Let L ≥ 1, ε > 0 be real numbers, (M, d) be a finite metric space and (N, ρ) be a metric space. A query to a metric space consists of a pair of points and asks for the distance between these points. We study the number of queries to metric spaces (M, d) and (N, ρ) needed to decide whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ∊-far from being L-bilipschitz embeddable into N, ρ). When (M, d) is ∊-far from being L-bilipschitz embeddable into (N, ρ), we allow an o(1) probability of error (i.e., returning the wrong answer "L-bilipschitz embeddable"). However, no error is allowed when (M, d) is L-bilipschitz embeddable into (N, ρ). That is, algorithms with only one-sided errors are studied in this paper. When |M| ≤ |N| are both finite, we give an upper bound of on the number of queries for determining with one-sided error whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ∊-far from being L-bilipschitz embeddable into (N, ρ). For the special case of finite |M| = |N|, the above upper bound evaluates to . We also prove a lower bound of Ω(|N|^3/2) for the special case when |M| = |N| are finite and L = 1, which coincides with testing isometry between finite metric spaces. For finite |M| = |N|, the upper and lower bounds thus match up to a multiplicative factor of at most , which depends only sublogarithmically in |N|. We also investigate the case when (N, ρ) is not necessarily finite. Our results are based on techniques developed in an earlier work on testing graph isomorphism.

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs.

This paper describes a random model for chemical graphs that captures the notion of valence along with algorithms to generate chemical graphs using this model. An approach for computing the probability that a particular chemical graph is generated under this model is provided. The model is also used to provide theoretical bounds on the accuracy of a class of canonical labeling algorithms for a class of hydrocarbons.

This paper proves that almost every $n$-vertex graph has the property that the multiset of its induced subgraphs on $3{log}_{2}n$ vertices is sufficient to determine it up to isomorphism. That is, the probability that there exists two $n$-vertex graphs with the same multiset of $3{log}_{2}n$-vertex induced subgraphs goes to zero as $n$ goes to infinity.

Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of an assignment algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.

A powerful and universal data structure with applications invarious subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem.

In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.

In this paper we present a fast algorithm for the computation of error-correcting graph isomorphisms. The new algorithm is an extension of a method for exact subgraph isomorphism detection from an input graph to a set of a priori known model graphs, which was previously developed by the authors. Similar to the original algorithm, the new method is based on the idea of creating a decision tree from the model graphs. This decision tree is compiled off-line in a preprocessing step. At run time, it is used to find all error-correcting graph isomorphisms from an input graph to any of the model graphs up to a certain degree of distortion. The main advantage of the new algorithm is that error-correcting graph isomorphism detection is guaranteed to require time that is only polynomial in terms of the size of the input graph. Furthermore, the time complexity is completely independent of the number of model graphs and the number of edges in each model graph. However, the size of the decision tree is exponential in the size of the model graphs and the degree of error. Nevertheless, practical experiments have indicated that the method can be applied to graphs containing up to 16 vertices.

Whittlesey^12,13,14 gave a criterion which decides when two finite 2-dimensional complexes are homeomorphic. We show that graph isomorphism can be reduced efficiently to 2-complex homeomorphism, and that Whittlesey's criterion can be reduced efficiently to graph isomorphism. Therefore graph isomorphism and 2-complex homeomorphism are polynomial-time equivalent.

Let be a finitely generated, arithmetical variety such that all subdirectly irreducible algebras from have linearly ordered congruences. We show that there is a polynomial time algorithm that tests the existing of an isomorphism between any two finite algebras from .

This includes the following classical structures in algebra:

• Boolean algebras.

• Varieties of rings generated by finitely many finite fields.

• Varieties of Heyting algebras generated by an n–element chain.

We consider zero divisors of an arbitrary real Cayley–Dickson algebra such that their components are both standard basis elements. We construct inductively the orthogonality graph on these elements. Then we show that, if we restrict our attention to at least $16$-dimensional algebras, two algebras are isomorphic if and only if their graphs are isomorphic. We also provide an algorithm to retrieve the Cayley–Dickson parameters of an algebra from its graph.

In this paper, two outwardly different graphs, namely, the zero-divisor graph $\mathrm{\Gamma }(C_c(X))$ and the comaximal graph ${\mathrm{\Gamma }}_2^{\prime }(C_c(X))$ of the ring $C_c(X)$ of all real-valued continuous functions having countable range, defined on any zero-dimensional space $X$, are investigated. It is observed that these two graphs exhibit resemblance, so far as the diameters, girths, connectedness, triangulatedness or hypertriangulatedness are concerned. However, the study reveals that the zero-divisor graph $\mathrm{\Gamma }(A_c(X))$ of an intermediate ring $A_c(X)$ of $C_c(X)$ is complemented if and only if the space of all minimal prime ideals of $A_c(X)$ is compact. Moreover, $\mathrm{\Gamma }(C_c(X))$ is complemented when and only when its subgraph $\mathrm{\Gamma }(A_c(X))$ is complemented. On the other hand, the comaximal graph of $C_c(X)$ is complemented if and only if the comaximal graph of its over-ring $C(X)$ is complemented and the latter graph is known to be complemented if and only if $X$ is a $P$-space. Indeed, for a large class of spaces (i.e. for perfectly normal, strongly zero-dimensional spaces which are not P-spaces), $\mathrm{\Gamma }(C_c(X))$ and ${\mathrm{\Gamma }}_2^{\prime }(C_c(X))$ are seen to be non-isomorphic. Defining appropriately the quotient of a graph, it is utilized to establish that for a discrete space $X$, $\mathrm{\Gamma }(C_c(X))$ (= $\mathrm{\Gamma }(C(X))$) and ${\mathrm{\Gamma }}_2^{\prime }(C_c(X))$ (= ${\mathrm{\Gamma }}_2^{\prime }(C(X))$) are isomorphic, if $X$ is at most countable. Under the assumption of continuum hypothesis, the converse of this result is also shown to be true.

For a group $G$ and a subset $S$ of $G$ the bi-Cayley graph BCay$(G,S)$ of $G$ with respect to $S$ is the bipartite graph with vertex set $G\times \{0,1\}$ and edge set $\{\{(x,0),(sx,1)\}|x\in G,s\in S\}$. A bi-Cayley graph BCay$(G,S)$ is called a BCI-graph if for any bi-Cayley graph BCay$(G,T)$, $\mathrm{\text{BCay}}(G,S)\cong \mathrm{\text{BCay}}(G,T)$ implies that $T=g{S}^{\alpha }$ for some $g\in G$ and $\alpha \in \mathrm{\text{Aut}}(G)$. A group $G$ is called a $m$-BCI-group if all bi-Cayley graphs of $G$ with valency at most $m$ are BCI-graphs. In this paper, we characterize the $m$-BCI dihedral groups for $m\le 3$. Also, we show that the dihedral group $D_{2p}$ ($p$ is prime) is a $4$-BCI-group.

In this paper, the new concept $i$-isodominism between two graphs is introduced, where $i$ is a positive integer. The $i$-isodominism is a pair of the graph isomorphism which depends on the smallest $i$-dominating sets. By this tool, a graph with one vertex, complete graphs, wheels and stars are in the same $1$-isodominism class. Furthermore, some results about the $1$-isodominism classes of paths, cycles and star polygon are presented.

A powerful and universal data structure with applications in various subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem.

In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.