The isomorphism problem is polynomially solvable for certain graph languages
| Autor: | Manfred Schnitzler |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Discrete mathematics
Voltage graph Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Graph canonization Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Graph homomorphism Graph isomorphism Tutte polynomial Graph automorphism Graph property Null graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 3540123105 Graph-Grammars and Their Application to Computer Science |
| DOI: | 10.1007/bfb0000119 |
| Popis: | Conditions are developed which for all graph grammars satisfying them ensure that the isomorphism problem for the corresponding graph languages is solvable in polynomial time. The suitability of these conditions is proved by the presentation of an algorithm scheme. A large number of graph grammars that satisfy the conditions give rise to the polynomial solvability of the isomorphism problem for graph classes, for which such results are mostly new. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|