18 citations · 46 across the 68 of their papers we have counts for
19 papers · 1 filter
Linear programming based approximation for unweighted induced matchings --- breaking the barrier
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induc…
Uniquely restricted matchings in subcubic graphs without short cycles
Maximilian Fürst, Dieter Rautenbach
A matching in a graph is uniquely restricted if no other matching in covers the same set of vertices. We prove that any connected subcubic graph with vertices and g…
Girth, minimum degree, independence, and broadcast independence
Stéphane Bessy, Dieter Rautenbach
An independent broadcast on a connected graph is a function such that, for every vertex of , the value is at most the eccentricity of …
Relating broadcast independence and independence
Stéphane Bessy, Dieter Rautenbach
An independent broadcast on a connected graph is a function such that, for every vertex of , the value is at most the eccentricity of …
Algorithmic aspects of broadcast independence
Stéphane Bessy, Dieter Rautenbach
An independent broadcast on a connected graph is a function such that, for every vertex of , the value is at most the eccentricity of …
The matching number of tree and bipartite degree sequences
F. Bock, D. Rautenbach
We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree de…