66 citations · 323 across the 55 of their papers we have counts for
6 papers · 1 filter
Complexity and algorithms for constant diameter augmentation problems
Eun Jung Kim, Martin Milanic, Jérôme Monnot +1
We study the following problem: for given integers and graph , can we obtain a graph with diameter via at most edge deletions ? We determine the computational comp…
On the degree sequences of dual graphs on surfaces
Endre Boros, Vladimir Gurvich, Martin Milanič +1
Given two graphs and with a one-to-one correspondence between their edges, when do and form a pair of dual graphs realizing the vertices and countries of a map…
Shifting paths to avoidable ones
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
An extension of an induced path in a graph is an induced path such that deleting the endpoints of results in . An induced path in a graph is said to be avoidab…
Strong cliques in diamond-free graphs
Nina Chiarelli, Berenice Martínez Barona, Martin Milanič +2
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques…
Treewidth versus clique number. I. Graph classes with a forbidden structure
Clément Dallard, Martin Milanič, Kenny Štorgel
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of…
Fair allocation of indivisible items with conflict graphs
Nina Chiarelli, Matjaž Krnc, Martin Milanič +3
We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility re…