4 papers
On the parameterized complexity of Broadcast Independence and Broadcast Packing
Joanne Dumont, Edouard Nemery, Anthony Perez +1
A broadcast on a connected graph is a function f that assigns each vertex v an integer f(v) with 0 <= f(v) <= ecc(v) where ecc(v) denotes the eccentricity of v. A vertex u hears a…
Fair Railway Network Design
Zixu He, Sirin Botan, Jérôme Lang +3
When designing a public transportation network in a country, one may want to minimise the sum of travel duration of all inhabitants. This corresponds to a purely utilitarian view a…
Generalizing Roberts' characterization of unit interval graphs
Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine +2
For any natural number , a graph is a (disjoint) -interval graph if it is the intersection graph of (disjoint) -intervals, the union of (disjoint) intervals on the…
Recognizing unit multiple intervals is hard
Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora +1
Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A -in…