Name
Abstract | ||
|---|---|---|
Many practical problems are modeled with networks and graphs. Their exploration is of significant importance, and several graph-exploration algorithms already exist. In this paper, we focus on a type of vertex equivalence, called exploratory equivalence, which has a great potential to speed up such algorithms. It is an equivalence based on graph automorphisms and can, for example, help us in solving the subgraph isomorphism problem, which is a well-known NP-hard problem. In particular, if a given pattern graph has nontrivial automorphisms, then each of its nontrivial exploratory equivalent classes gives rise to a set of constraints to prune the search space of solutions. In the paper, we define the maximum exploratory equivalence problem. We show that the defined problem is at least as hard the graph isomorphism problem. Additionally, we present a polynomial-time algorithm for solving the problem when the input is restricted to tree graphs. Furthermore, we show that for trees, a maximum exploratory equivalent partition leads to a globally optimal set of subgraph isomorphism constraints, whereas this is not necessarily the case for general graphs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.15439/2015F329 | 2015 Federated Conference on Computer Science and Information Systems (FedCSIS) |
Keywords | Field | DocType |
maximum exploratory equivalence problem,graph-exploration algorithms,vertex equivalence,graph automorphisms,NP-hard problem,nontrivial automorphisms,search space,tree graphs,polynomial-time algorithm,subgraph isomorphism constraints,general graphs | Discrete mathematics,Combinatorics,Tree (graph theory),Graph isomorphism,Maximum common subgraph isomorphism problem,Automorphism,Induced subgraph isomorphism problem,Equivalence (measure theory),Mathematics,Graph isomorphism problem,Subgraph isomorphism problem | Conference |
Volume | ISSN | Citations |
5 | 2300-5963 | 0 |
PageRank | References | Authors |
0.34 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luka Fürst | 1 | 19 | 2.72 |
| Uros Cibej | 2 | 132 | 8.07 |
| Jurij Mihelič | 3 | 5 | 3.16 |