8 citations · 12 across the 8 of their papers we have counts for
10 papers
Sandwich Monotonicity and Recognition of Weighted Graph Classes
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +5
Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from…
A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
Martin Milanič, Nevena Pivač
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 po…
Bisimplicial separators
Martin Milanič, Irena Penev, Nevena Pivač +1
A minimal separator of a graph is a set such that there exist vertices with the property that separates from in , b…
Computing Well-Covered Vector Spaces of Graphs using Modular Decomposition
Martin Milanič, Nevena Pivač
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…
Allocation of Indivisible Items with Individual Preference Graphs
Nina Chiarelli, Clément Dallard, Andreas Darmann +5
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…
Graphs where Search Methods are Indistinguishable
Matjaž Krnc, Nevena Pivač
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 o…
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…
Minimal separators in graph classes defined by small forbidden induced subgraphs
Martin Milanič, Nevena Pivač
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-t…
Recognizing Graph Search Trees
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
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 span…
On the End-Vertex Problem of Graph Searches
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
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 e…