3 citations · 7 across the 12 of their papers we have counts for
13 papers · 1 filter
The 3-dicritical semi-complete digraphs
Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta
A digraph is -dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that…
Complexity results on the decomposition of a digraph into directed linear forests and out-stars
Florian Hörsch, Lucas Picasarri-Arrieta
We consider two decomposition problems in directed graphs. We say that a digraph is -bounded for some if each of its connected components contains at…
On orientations maximizing total arc-connectivity
Florian Hörsch
For a given digraph and distinct , we denote by the local arc-connectivity from to . Further, we define the total arc-connectivity of $…
Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
Jørgen Bang-Jensen, Florian Hörsch, Matthias Kriesell
By a well known theorem of Robbins, a graph has a strongly connected orientation if and only if is 2-edge-connected and it is easy to find, in linear time, either a cut edg…
On the minimum number of inversions to make a digraph -(arc-)strong
Julien Duron, Frédéric Havet, Florian Hörsch +1
The {\it inversion} of a set of vertices in a digraph consists of reversing the direction of all arcs of . We study (resp. ) whic…
Decompositions into two linear forests of bounded lengths
Rutger Campbell, Florian Hörsch, Benjamin Moore
For some , we call a linear forest -bounded if each of its components has at most edges. We will say a -bounded linear forest…
Problems, proofs, and disproofs on the inversion number
Guillaume Aubian, Frédéric Havet, Florian Hörsch +4
The {\it inversion} of a set of vertices in a digraph consists in reversing the direction of all arcs of . The {\it inversion number} of an oriented grap…
Steiner connectivity problems in hypergraphs
Florian Hörsch, Zoltán Szigeti
We say that a tree is an -Steiner tree if and a hypergraph is an -Steiner hypertree if it can be trimmed to an -Steiner tree. We prove that it is NP…
Rainbow bases in matroids
Florian Hörsch, Tomáš Kaiser, Matthias Kriesell
Recently, it was proved by Bérczi and Schwarcz that the problem of factorizing a matroid into rainbow bases with respect to a given partition of its ground set is algorithmically i…
On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
Florian Hörsch, Zoltán Szigeti
We show that the problem of deciding whether a given graph has a well-balanced orientation such that for all for a given f…
A note on 2-vertex-connected orientations
Florian Hörsch, Zoltán Szigeti
We consider two possible extensions of a theorem of Thomassen characterizing the graphs admitting a 2-vertex-connected orientation. First, we show that the problem of deciding whet…
Checking the admissibility of odd-vertex pairings is hard
Florian Hörsch
Nash-Williams proved that every graph has a well-balanced orientation. A key ingredient in his proof is admissible odd-vertex pairings. We show that for two slightly different defi…
Reachability in arborescence packings
Florian Hörsch, Zoltán Szigeti
Fortier et al. proposed several research problems on packing arborescences. Some of them were settled in that article and others were solved later by Matsuoka and Tanigawa and by G…