Abstract | ||
---|---|---|
If a graph-theoretical property is compatible with the derivation process of hyperedge replacement graph grammars in a certain way, the property turns out to be decidable for the corresponding graph languages. More exactly speaking, we consider two questions:(1)Is there a graph in the generated language having the property?(2)Do all graphs in the generated language have the property?In both cases, we get decidability for all hyperedge replacement graph grammars as inputs. Colorability, Hamiltonicity, and planarity are shown to be compatible so that our decidability results apply to them. |
Year | DOI | Venue |
---|---|---|
1989 | 10.1007/BF00288976 | Acta Inf. |
Keywords | Field | DocType |
Information System,Operating System,Data Structure,Communication Network,Information Theory | Discrete mathematics,Combinatorics,Line graph,Forbidden graph characterization,Graph property,Computer science,Cubic graph,Null graph,Symmetric graph,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
26 | 7 | 0001-5903 |
Citations | PageRank | References |
24 | 1.91 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Annegret Habel | 1 | 234 | 23.18 |
Hans-jörg Kreowski | 2 | 298 | 37.05 |
Walter Vogler | 3 | 354 | 41.25 |