31 citations · 37 across the 10 of their papers we have counts for
10 papers
Perfect phylogenies via the Minimum Uncovering Branching problem: efficiently solvable cases
Narmina Baghirova, Esther Galby, Martin Milanič
In this paper, we present new efficiently solvable cases of the Minimum Uncovering Branching problem, an optimization problem with applications in cancer genomics introduced by Huj…
Layered tree-independence number and clique-based separators
Clément Dallard, Martin Milanič, Andrea Munaro +1
Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublin…
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Clément Dallard, Matjaž Krnc, O-joung Kwon +4
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes de…
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…
Fair Allocation Algorithms for Indivisible Items under Structured Conflict Constraints
Nina Chiarelli, Matjaž Krnc, Martin Milanič +2
We consider the fair allocation of indivisible items to several agents with additional conflict constraints. These are represented by a conflict graph where each item corresponds t…
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…