Algorithms for graph problems on BNLC structured graphs

We present algorithms for analyzing single graphs and sets of graphs generated by boundary node label controlled (BNLC) graph grammars. This paper extends a unified framework for developing algorithms on context-free graph languages to BNLC graph languages. Graphs in BNLC graph languages do not necessarily have vertex separators of bounded size as do graphs in context-free graph languages. We give combinatorial decision and query algorithms on single graphs generated by a deterministic BNLC graph grammar and algorithms for the following question: Does the language of a given BNLC graph grammar contain a graph that fulfills a certain graph property? All algorithms developed in this paper consider the graph grammar as input.

Authors

• Egon Wanke

Keywords

No keywords are indexed for this paper.