13 citations · 48 across the 26 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017★ 1 cited
Being even slightly shallow makes life hard
Irene Muzi, Michael P. O'Brien, Felix Reidl +1
We study the computational complexity of identifying dense substructures, namely -shallow topological minors and -subdivisions. Of particular interest is the case when $r=1…
cs.CC2016
Width, depth and space
Li-Hsuan Chen, Felix Reidl, Peter Rossmanith +1
The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of inter…
cs.CC2014
Zig-Zag Numberlink is NP-Complete
Aaron Adcock, Erik D. Demaine, Martin L. Demaine +4
When can terminal pairs in an grid be connected by vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our ha…