The complexity of the K_n,n-problem for node replacement graph languages

DOI10.1006/INCO.2000.3021MaRDI QIDQ1854438zbMATH OpenOpenAlexFDO

Authors Konstantin Skodinis

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.2000.3021

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• The complexity of graph languages generated by hyperedge replacement
• NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
• Publication:4502809
• scientific article; zbMATH DE number 177465
• Node replacement graph languages squeezed with chains, trees, and forests
• The subgraph isomorphism problem on a class of hyperedge replacement languages
• Node replacement graph grammars with dynamic node relabeling
• Node replacement in hypergraphs: simulation of hyperedge replacement, and decidability of confluence
• The complexity of connectivity problems on context-free graph languages
• scientific article; zbMATH DE number 17563

Cites work

• A comparison of boundary graph grammars and context-free hypergraph grammars
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Boundary graph grammars with dynamic edge relabeling
• Easy problems for tree-decomposable graphs
• Emptiness problems of eNCE graph languages
• Formal languages of labelled graphs
• Graph expressions and graph rewritings
• Handbook of Graph Grammars and Computing by Graph Transformation
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3943061 (Why is no real title available?)
• scientific article; zbMATH DE number 17539 (Why is no real title available?)
• scientific article; zbMATH DE number 1107740 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• Languages that Capture Complexity Classes
• Linear graph grammars: Power and complexity
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Structural properties of context-free sets of graphs generated by vertex replacement
• The bounded degree problem for eNCE graph grammars
• The bounded degree problem for NLC grammars is decidable

Cited in

(4)

• NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
• The bounded degree problem for eNCE graph grammars
• scientific article; zbMATH DE number 177465 (Why is no real title available?)
• scientific article; zbMATH DE number 1107740 (Why is no real title available?)

This page was built for publication: The complexity of the \(K_{n,n}\)-problem for node replacement graph languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854438)