Martin Milanič | DeepAI

AI Chat

Featured Co-authors

Daniël Paulusma
59 publications
Fedor V. Fomin
59 publications
Petr A. Golovach
55 publications
Édouard Bonnet
45 publications
Paweł Rzążewski
43 publications
Robert Ganian
39 publications
Matthew Alastair Johnson
35 publications
Dušan Knop
31 publications
Sebastian Ordyniak
31 publications
Hans L. Bodlaender
29 publications
Stefan Kratsch
26 publications

∙ 08/31/2023

Dually conformal hypergraphs

Given a hypergraph ℋ, the dual hypergraph of ℋ is the hypergraph of all ...

0 Endre Boros, et al. ∙

∙ 08/18/2023

Fair Allocation Algorithms for Indivisible Items under Structured Conflict Constraints

We consider the fair allocation of indivisible items to several agents w...

0 Nina Chiarelli, et al. ∙

∙ 01/24/2023

Treewidth is NP-Complete on Cubic Graphs (and related results)

In this paper, we give a very simple proof that Treewidth is NP-complete...

0 Hans L. Bodlaender, et al. ∙

∙ 01/23/2023

Functionality of box intersection graphs

Functionality is a graph complexity measure that extends a variety of pa...

0 Clément Dallard, et al. ∙

∙ 12/16/2022

Computing Well-Covered Vector Spaces of Graphs using Modular Decomposition

A graph is well-covered if all its maximal independent sets have the sam...

0 Martin Milanič, et al. ∙

∙ 10/01/2022

Conditions for minimally tough graphs

Katona, Soltész, and Varga showed that no induced subgraph can be exclud...

0 Clément Dallard, et al. ∙

∙ 09/25/2022

Tree decompositions with bounded independence number: beyond independent sets

We continue the study of graph classes in which the treewidth can only b...

0 Martin Milanič, et al. ∙

∙ 08/26/2022

Avoidability beyond paths

The concept of avoidable paths in graphs was introduced by Beisegel, Chu...

0 Vladimir Gurvich, et al. ∙

∙ 07/20/2022

Computing Tree Decompositions with Small Independence Number

The independence number of a tree decomposition is the maximum of the in...

0 Clément Dallard, et al. ∙

∙ 06/30/2022

Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure

We continue the study of (tw,ω)-bounded graph classes, that is, heredita...

0 Clément Dallard, et al. ∙

∙ 02/09/2022

Allocation of Indivisible Items with Individual Preference Graphs

This paper studies the allocation of indivisible items to agents, when e...

0 Nina Chiarelli, et al. ∙

∙ 11/08/2021

Tree decompositions with bounded independence number and their algorithmic applications

In 2020, Dallard, Milanič, and Štorgel initiated a systematic study of g...

0 Clément Dallard, et al. ∙

∙ 06/18/2021

Graphs with at most two moplexes

A moplex is a natural graph structure that arises when lifting Dirac's c...

0 Clément Dallard, et al. ∙

∙ 08/03/2020

Shifting paths to avoidable ones

An extension of an induced path P in a graph G is an induced path P' suc...

0 Vladimir Gurvich, et al. ∙

∙ 08/02/2020

On the degree sequences of dual graphs on surfaces

Given two graphs G and G^* with a one-to-one correspondence between thei...

0 Endre Boros, et al. ∙

∙ 06/10/2020

Treewidth versus clique number in graph classes with a forbidden structure

Treewidth is an important graph invariant, relevant for both structural ...

0 Clément Dallard, et al. ∙

∙ 03/25/2020

Fair packing of independent sets

In this work we add a graph theoretical perspective to a classical probl...

0 Nina Chiarelli, et al. ∙

∙ 07/28/2019

Avoidable Vertices and Edges in Graphs

A vertex in a graph is simplicial if its neighborhood forms a clique. We...

0 Jesse Beisegel, et al. ∙

∙ 12/13/2018

Mind the Independence Gap

The independence gap of a graph was introduced by Ekim et al. (2018) as ...

0 Tınaz Ekim, et al. ∙

∙ 12/13/2018

A characterization of claw-free CIS graphs and new results on the order of CIS graphs

A graph is CIS if every maximal clique interesects every maximal stable ...

0 Liliana Alcón, et al. ∙

∙ 08/24/2018

Detecting strong cliques

A strong clique in a graph is a clique intersecting every maximal indepe...

0 Ademir Hujdurović, et al. ∙

∙ 08/03/2018

Searching for square-complementary graphs: non-existence results and complexity of recognition

A graph is square-complementary (squco, for short) if its square and com...

0 Ratko Darda, et al. ∙

∙ 05/12/2018

Bipartite Graphs of Small Readability

We study a parameter of bipartite graphs called readability, introduced ...

0 Rayan Chikhi, et al. ∙

∙ 05/09/2018

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs

A hypergraph H is said to be 1-Sperner if for every two hyperedges the s...

0 Endre Boros, et al. ∙

∙ 03/12/2018

New Algorithms for Weighted k-Domination and Total k-Domination Problems in Proper Interval Graphs

Given a positive integer k, a k-dominating set in a graph G is a set of ...

0 Nina Chiarelli, et al. ∙

∙ 08/15/2017

Almost Well-Covered Graphs Without Short Cycles

We study graphs in which the maximum and the minimum sizes of a maximal ...

0 Tınaz Ekim, et al. ∙

∙ 06/25/2017

Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity

We perform a systematic study in the computational complexity of the con...

0 Nina Chiarelli, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world