Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Pivač, Nevena"'
A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
Autor:
Milanič, Martin, Pivač, Nevena
A minimal separator in a graph is an inclusion-minimal set of vertices that separates some fixed pair of nonadjacent vertices. A graph class is said to be tame if there exists a polynomial upper bound for the number of minimal separators of every gra
Externí odkaz:
http://arxiv.org/abs/2405.15543
A minimal separator of a graph $G$ is a set $S \subseteq V(G)$ such that there exist vertices $a,b \in V(G) \setminus S$ with the property that $S$ separates $a$ from $b$ in $G$, but no proper subset of $S$ does. For an integer $k\ge 0$, we say that
Externí odkaz:
http://arxiv.org/abs/2312.10830
Autor:
Milanič, Martin, Pivač, Nevena
A graph is well-covered if all its maximal independent sets have the same cardinality. This well studied concept was introduced by Plummer in 1970 and naturally generalizes to the weighted case. Given a graph $G$, a real-valued vertex weight function
Externí odkaz:
http://arxiv.org/abs/2212.08599
Autor:
Chiarelli, Nina, Dallard, Clément, Darmann, Andreas, Lendl, Stefan, Milanič, Martin, Muršič, Peter, Pferschy, Ulrich, Pivač, Nevena
This paper studies the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph. The vertices of each preference graph represent the subset of items approved of by the respective agen
Externí odkaz:
http://arxiv.org/abs/2202.04465
Autor:
Krnc, Matjaž, Pivač, Nevena
Graph searching is one of the simplest and most widely used tools in graph algorithms. Every graph search method is defined using some particular selection rule, and the analysis of the corresponding vertex orderings can aid greatly in devising algor
Externí odkaz:
http://arxiv.org/abs/2109.00035
Autor:
Chiarelli, Nina, Krnc, Matjaž, Milanič, Martin, Pferschy, Ulrich, Pivač, Nevena, Schauer, Joachim
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 relation between pairs of items described in terms of a conflict graph.
Externí odkaz:
http://arxiv.org/abs/2003.11313
Autor:
Chiarelli, Nina, Dallard, Clément, Darmann, Andreas, Lendl, Stefan, Milanič, Martin, Muršič, Peter, Pferschy, Ulrich, Pivač, Nevena
Publikováno v:
In Discrete Applied Mathematics 31 July 2023 334:45-62
Autor:
Milanič, Martin, Pivač, Nevena
Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number
Externí odkaz:
http://arxiv.org/abs/1903.04534
Autor:
Beisegel, Jesse, Denkert, Carolin, Köhler, Ekkehard, Krnc, Matjaž, Pivač, Nevena, Scheffler, Robert, Strehler, Martin
Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given spanning tree of a graph is a search tree of a particular search on this g
Externí odkaz:
http://arxiv.org/abs/1811.09249
Autor:
Beisegel, Jesse, Denkert, Carolin, Köhler, Ekkehard, Krnc, Matjaž, Pivač, Nevena, Scheffler, Robert, Strehler, Martin
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 21 no. 1, ICGT 2018 (June 13, 2019) dmtcs:4937
End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an end-vertex of a particular search was first introduced by Corneil, K\"o
Externí odkaz:
http://arxiv.org/abs/1810.12253