13 citations · 48 across the 26 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DS2019
Domination above r-independence: does sparseness help?
Carl Einarson, Felix Reidl
Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound…
cs.DM2019
Longest paths in 2-edge-connected cubic graphs
Nikola K. Blanchard, Eldar Fischer, Oded Lachish +1
We prove almost tight bounds on the length of paths in -edge-connected cubic graphs. Concretely, we show that (i) every -edge-connected cubic graph of size has a path of…