2 citations · 2 across the 3 of their papers we have counts for
5 papers
Relaxing the Irrevocability Requirement for Online Graph Algorithms
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +1
Online graph problems are considered in models where the irrevocability requirement is relaxed. Motivated by practical examples where, for example, there is a cost associated with…
Online Dominating Set
Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt +2
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online a…
Equimatchable factor-critical graphs and independence number 2
Eduard Eiben, Michal Kotrbcik
A graph is equimatchable if each of its matchings is a subset of a maximum matching. It is known that any 2-connected equimatchable graph is either bipartite, or factor-critical, a…
Simple greedy 2-approximation algorithm for the maximum genus of a graph
Michal Kotrbcik, Martin Skoviera
The maximum genus of a graph G is the largest genus of an orientable surface into which G has a cellular embedding. Combinatorially, it coincides with the maximum number o…
Genus Distributions of cubic series-parallel graphs
Jonathan L. Gross, Michal Kotrbčík, Timothy Sun
We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of max…