Recognising \(k\)-connected hypergraphs in cubic time

DOI10.1016/0304-3975(93)90065-2zbMath0779.68052OpenAlexW2040035445MaRDI QIDQ685463

Frank Drewes

Publication date: 19 January 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90065-2

zbMATH Keywords

hypergraphdecompositiongraph parsinghyperedge-replacement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Theory of compilers and interpreters (68N20)

Related Items (6)

Uniform parsing for hyperedge replacement grammars ⋮ Predictive Top-Down Parsing for Hyperedge Replacement Grammars ⋮ Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement ⋮ Spreading linear triple systems and expander triple systems ⋮ The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs ⋮ NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)

Cites Work

• Hyperedge replacement: grammars and languages
• String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The complexity of graph languages generated by hyperedge replacement
• A structural characterization of planar combinatorial graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Dividing a Graph into Triconnected Components
• Recognition and parsing of context-free languages in time n3
• Counter machines and counter languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Recognising \(k\)-connected hypergraphs in cubic time