5 citations · 12 across the 10 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2015
Maximum Pagenumber-k Subgraph is NP-Complete
Peter Jonsson, Marco Kuhlmann
Given a graph with a total order defined on its vertices, the Maximum Pagenumber- Subgraph Problem asks for a maximum subgraph of such that can be embedded int…
cs.CC2008★ 1 cited
Ogden's Lemma for Regular Tree Languages
Marco Kuhlmann
We motivate and prove a strong pumping lemma for regular tree languages. The new lemma can be seen as the natural correspondent of Ogden's lemma for context-free string languages.