1 citations · 1 across the 2 of their papers we have counts for
4 papers · 1 filter
The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +3
We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called the simultaneous interval number. This parameter is related to the simultane…
Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Paloma T. Lima, Martin Milanič, Peter Muršič +3
For a tree decomposition of a graph , by we denote the size of a largest induced matching in all of whose edges intersect one bag of $\mathcal…
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the i…
Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
We consider the task of allocating indivisible items to agents, when the agents' preferences over the items are identical. The preferences are captured by means of a directed acycl…