Graph grammars and the complexity gap in the isomorphism problem for acyclic digraphs
| Autor: | Manfred Schnitzler |
|---|---|
| Rok vydání: | 1981 |
| Předmět: |
Discrete mathematics
Subgraph isomorphism problem Maximum common subgraph isomorphism problem Graph canonization Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Induced subgraph isomorphism problem Graph homomorphism Graph isomorphism Graph automorphism Graph property MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Graphtheoretic Concepts in Computer Science ISBN: 9783540102915 WG |
| DOI: | 10.1007/3-540-10291-4_11 |
| Popis: | We regard several classes of acyclic digraphs forming a hierarchy, which represents the present complexity gap in the isomorphism problem for acyclic digraphs. The classes at the lowest level of the hierarchy have a polynomially solvable isomorphism problem, whereas the more general ones have an isomorphism complete one. For all classes we develop graph grammars and examine them for properties reflecting the complexity of the corresponding isomorphism problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|