Undecidability of Winkler's \(r\)-neighborhood problem for covering digraphs
DOI10.1006/JCTB.1994.1017zbMATH Open0790.03045OpenAlexW2038845590MaRDI QIDQ1322019
Publication date: 6 June 1994
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1994.1017
undecidabilitydecision problemcontext-free grammar\(r\)-neighborhoodscovering digraph of a partial ordering
Combinatorics of partially ordered sets (06A07) Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Directed graphs (digraphs), tournaments (05C20)
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- An undecidability result on limits of sparse graphs 👍 👎
- On the complexity of cover-incomparability graphs of posets 👍 👎
- On the weighted complexity of a regular covering of a graph 👍 👎
- Complexity results for well‐covered graphs 👍 👎
- k-Neighborhood-Covering and -Independence Problems for Chordal Graphs 👍 👎
- Neighborhood unions and the cycle cover number of a graph 👍 👎
- Undecidability of linear inequalities in graph homomorphism densities 👍 👎
- Thek-neighbourhood-covering problem on interval graphs 👍 👎
This page was built for publication: Undecidability of Winkler's \(r\)-neighborhood problem for covering digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322019)
