66 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- University of LjubljanaSI66 papers
- Institute of Mathematics, Physics, and MechanicsSI50 papers
- The University of Western AustraliaAU11 papers
- Centre National de la Recherche ScientifiqueFR10 papers
- University of Milano-BicoccaIT10 papers
- University of NisRS9 papers
- Eötvös Loránd UniversityHU7 papers
- Mississippi State UniversityUS7 papers
- National Research University Higher School of EconomicsRU7 papers
- University of MariborSI7 papers
- AGH University of KrakowPL6 papers
- École Normale Supérieure de LyonFR6 papers
15 papers · 1 filter
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…
An efficient algorithm for generating transmission irregular trees
Ivan Stošić, Ivan Damnjanović
The transmission of a vertex in a connected graph is the sum of distances from that vertex to all the other vertices. A connected graph is transmission irregular if any two distinc…
Counting the number of inequivalent arithmetic expressions on variables
Ivan Stošić, Ivan Damnjanović, Žarko Ranđelović
An expression is any mathematical formula that contains certain formal variables and operations to be executed in a specified order. In computer science, it is usually convenient t…
Colourful components in -caterpillars and planar graphs
Janka Chlebíková, Clément Dallard
A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected compone…
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…
Bipartite Graphs of Small Readability
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch +4
We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bio…
On Almost Well-Covered Graphs of Girth at Least 6
Tınaz Ekim, Didem Gözüpek, Ademir Hujdurović +1
We consider a relaxation of the concept of well-covered graphs, which are graphs with all maximal independent sets of the same size. The extent to which a graph fails to be well-co…
Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
Didem Gözüpek, Ademir Hujdurović, Martin Milanič
A graph is said to be well-dominated if all its minimal dominating sets are of the same size. The class of well-dominated graphs forms a subclass of the well studied class of well-…
Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem
Ademir Hujdurović, Edin Husić, Martin Milanič +2
Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, to appear) introduced the minimum confli…
On the complexity of the vector connectivity problem
Ferdinando Cicalese, Martin Milanič, Romeo Rizzi
We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph with a requirement for each vertex , VecCon asks for a minim…
Polynomial-time Algorithms for Weighted Efficient Domination Problems in AT-free Graphs and Dually Chordal Graphs
Andreas Brandstädt, Pavel Fičur, Arne Leitert +1
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient…
New Polynomial Cases of the Weighted Efficient Domination Problem
Andreas Brandstädt, Martin Milanic, Ragnar Nevries
Let G be a finite undirected graph. A vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G i…
Set graphs. II. Complexity of set graph recognition and similar problems
Martin Milanič, Romeo Rizzi, Alexandru I. Tomescu
A graph is said to be a `set graph' if it admits an acyclic orientation that is also `extensional', in the sense that the out-neighborhoods of its vertices are pairwise distinc…
On the approximability and exact algorithms for vector domination and related problems in graphs
Ferdinando Cicalese, Martin Milanic, Ugo Vaccaro
We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that a…
The Plane-Width of Graphs
Marcin Kaminski, Paul Medvedev, Martin Milanic
Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the…