Context-free grammars as a tool for describing polynomial-time subclasses of hard problems

DOI10.1016/0020-0190(82)90086-2zbMath0486.68034MaRDI QIDQ1164998

A. O. Slisenko

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90086-2

zbMATH Keywords

polynomial-time algorithm; Hamiltonian circuit problem; context-free graph grammar

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

68N20: Theory of compilers and interpreters

05C38: Paths and cycles

Related Items

Parallel algorithms for a class of graphs generated recursively, Undecidability of the bandwidth problem on linear graph languages, Tree-like parse and polynomial subclasses of search problems, String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing, Metatheorems for decision problems on hyperedge replacement graph languages, Power properties of NLC graph grammars with a polynomial membership problem, Tree-width and the monadic quantifier hierarchy., Generating irregular partitionable data structures, The complexity of graph languages generated by hyperedge replacement

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Context-free graph grammars