Zobrazeno 1 - 10
of 282
pro vyhledávání: '"Paschos, Vangelis Th."'
An upper dominating set is a minimal dominating set in a graph. In the \textsc{Upper Dominating Set} problem, the goal is to find an upper dominating set of maximum size. We study the complexity of parameterized algorithms for \textsc{Upper Dominatin
Externí odkaz:
http://arxiv.org/abs/2101.07550
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 23 no. 1, Discrete Algorithms (April 30, 2021) dmtcs:6824
A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions. In particul
Externí odkaz:
http://arxiv.org/abs/1911.08964
In the $d$-Scattered Set problem we are asked to select at least $k$ vertices of a given graph, so that the distance between any pair is at least $d$. We study the problem's (in-)approximability and offer improvements and extensions of known results
Externí odkaz:
http://arxiv.org/abs/1910.05589
Autor:
Paschos, Vangelis Th.
The paper presents a polynomial time approximation schema for the edge-weighted version of maximum k-vertex cover problem in bipartite graphs.
Externí odkaz:
http://arxiv.org/abs/1909.08435
The average-case complexity of a branch-and-bound algorithms for Minimum Dominating Set problem in random graphs in the G(n,p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending
Externí odkaz:
http://arxiv.org/abs/1902.01874