5 papers
Arc-consistency with linear programming reduced costs (applied to stable set in chordal graphs)
Guillaume Claus, Hadrien Cambazard, Hugo Apeloig +1
A well known technique to reduce the search space in integer programming is known as variable fixing or reduced cost strengthening. The reduced costs given by an optimal dual solut…
Determining a graph from its reconfiguration graph
Gaétan Berthe, Caroline Brosse, Brian Hearn +3
Given a graph and a natural number , the -recolouring graph is the graph whose vertices are the -colourings of and whose edges link pairs of col…
Augmenting a hypergraph to have a matroid-based -bounded -limited packing of rooted hypertrees
Pierre Hoppenot, Zoltán Szigeti
The aim of this paper is to further develop the theory of packing trees in a graph. We first prove the classic result of Nash-Williams \cite{NW} and Tutte \cite{Tu} on packing span…
On arborescence packing augmentation in hypergraphs
Pierre Hoppenot, Zoltán Szigeti
We deepen the link between two classic areas of combinatorial optimization: augmentation and packing arborescences. We consider the following type of questions: What is the minimum…
Regular packing of rooted hyperforests with root constraints in hypergraphs
Pierre Hoppenot, Mathis Martin, Zoltán Szigeti
The seminal papers of Edmonds \cite{Egy}, Nash-Williams \cite{NW} and Tutte \cite{Tu} have laid the foundations of the theories of packing arborescences and packing trees. The dire…