5 citations · 10 across the 9 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.DS2023
Computing complexity measures of degenerate graphs
Pål Grønås Drange, Patrick Greaves, Irene Muzi +1
We show that the VC-dimension of a graph can be computed in time , where is the degeneracy of the input graph. The core idea of our algorithm is a data s…
math.CO2023★ 1 cited
Decomposition of (infinite) digraphs along directed 1-separations
Nathan Bowler, Florian Gut, Meike Hatzel +3
We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the s…