Recognising k-connected hypergraphs in cubic time
From MaRDI portal
Publication:685463
DOI10.1016/0304-3975(93)90065-2zbMATH Open0779.68052OpenAlexW2040035445MaRDI QIDQ685463FDOQ685463
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
Recommendations
- NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
- scientific article
- scientific article
- 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
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)
Cites Work
- Hyperedge replacement: grammars and languages
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Recognition and parsing of context-free languages in time n3
- Dividing a Graph into Triconnected Components
- Title not available (Why is that?)
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Counter machines and counter languages
- Title not available (Why is that?)
- String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
- Title not available (Why is that?)
- The complexity of graph languages generated by hyperedge replacement
- A structural characterization of planar combinatorial graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (8)
- Predictive Top-Down Parsing for Hyperedge Replacement Grammars
- NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
- The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
- Cubic time recognition of cocircuit graphs of uniform oriented matroids
- Uniform parsing for hyperedge replacement grammars
- Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement
- Recognizing hyperelliptic graphs in polynomial time
- Spreading linear triple systems and expander triple systems
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)
