Recognising k-connected hypergraphs in cubic time

DOI10.1016/0304-3975(93)90065-2MaRDI QIDQ685463zbMATH OpenOpenAlexFDO

Authors 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

decompositionhypergraphgraph parsinghyperedge-replacement

Mathematics Subject Classification ID

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

Recommendations

• NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
• scientific article; zbMATH DE number 177465
• scientific article; zbMATH DE number 4060748
• Powerful and NP-complete: hypergraph Lambek grammars
• Structural properties of context-free sets of graphs generated by vertex replacement
• A characterization of the sets of hypertrees generated by hyperedge-replacement graph grammars
• scientific article; zbMATH DE number 219258
• scientific article; zbMATH DE number 809155
• Uniform parsing for hyperedge replacement grammars
• scientific article; zbMATH DE number 5842462

Cites work

• scientific article; zbMATH DE number 4035178 (Why is no real title available?)
• scientific article; zbMATH DE number 4053039 (Why is no real title available?)
• scientific article; zbMATH DE number 4060749 (Why is no real title available?)
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 177465 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A structural characterization of planar combinatorial graphs
• Counter machines and counter languages
• Dividing a Graph into Triconnected Components
• Graph minors. II. Algorithmic aspects of tree-width
• Hyperedge replacement: grammars and languages
• Recognition and parsing of context-free languages in time n3
• String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
• The complexity of graph languages generated by hyperedge replacement
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

Cited in

(8)

• NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
• Spreading linear triple systems and expander triple systems
• Uniform parsing for hyperedge replacement grammars
• Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement
• Cubic time recognition of cocircuit graphs of uniform oriented matroids
• Recognizing hyperelliptic graphs in polynomial time
• Predictive top-down parsing for hyperedge replacement grammars
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs

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

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