Search Results

Documents authored by Kotrbcík, Michal

Found 2 Possible Name Variants:

Kotrbcík, Michal

Document
DOI: 10.4230/OASIcs.SOSA.2019.14
Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph

Authors: Michal Kotrbcík and Martin Skoviera

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
The maximum genus gamma_M(G) 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 of disjoint pairs of adjacent edges of G whose removal results in a connected spanning subgraph of G. In this paper we describe a greedy 2-approximation algorithm for maximum genus by proving that removing pairs of adjacent edges from G arbitrarily while retaining connectedness leads to at least gamma_M(G)/2 pairs of edges removed. As a consequence of our approach we also obtain a 2-approximate counterpart of Xuong's combinatorial characterisation of maximum genus.
Cite as

Michal Kotrbcík and Martin Skoviera. Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kotrbcik_et_al:OASIcs.SOSA.2019.14,
  author =	{Kotrbc{\'\i}k, Michal and Skoviera, Martin},
  title =	{{Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{14:1--14:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.14},
  URN =		{urn:nbn:de:0030-drops-100409},
  doi =		{10.4230/OASIcs.SOSA.2019.14},
  annote =	{Keywords: maximum genus, embedding, graph, greedy algorithm}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.21
Online Dominating Set

Authors: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper is devoted to the online dominating set problem and its variants on trees, bipartite, bounded-degree, planar, and general graphs, distinguishing between connected and not necessarily connected graphs. We believe this paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. In most cases, we obtain tight bounds on the competitive ratios. Our results show that requiring the graphs to be presented in a connected fashion allows the online algorithms to obtain provably better solutions. Furthermore, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage.
Cite as

Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen. Online Dominating Set. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2016.21,
  author =	{Boyar, Joan and Eidenbenz, Stephan J. and Favrholdt, Lene M. and Kotrbcik, Michal and Larsen, Kim S.},
  title =	{{Online Dominating Set}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.21},
  URN =		{urn:nbn:de:0030-drops-60434},
  doi =		{10.4230/LIPIcs.SWAT.2016.21},
  annote =	{Keywords: online algorithms, dominating set, competitive analysis, graph classes, connected graphs}
}

Kotrbcik, Michal

Document
DOI: 10.4230/OASIcs.SOSA.2019.14
Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph

Authors: Michal Kotrbcík and Martin Skoviera

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
The maximum genus gamma_M(G) 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 of disjoint pairs of adjacent edges of G whose removal results in a connected spanning subgraph of G. In this paper we describe a greedy 2-approximation algorithm for maximum genus by proving that removing pairs of adjacent edges from G arbitrarily while retaining connectedness leads to at least gamma_M(G)/2 pairs of edges removed. As a consequence of our approach we also obtain a 2-approximate counterpart of Xuong's combinatorial characterisation of maximum genus.
Cite as

Michal Kotrbcík and Martin Skoviera. Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kotrbcik_et_al:OASIcs.SOSA.2019.14,
  author =	{Kotrbc{\'\i}k, Michal and Skoviera, Martin},
  title =	{{Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{14:1--14:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.14},
  URN =		{urn:nbn:de:0030-drops-100409},
  doi =		{10.4230/OASIcs.SOSA.2019.14},
  annote =	{Keywords: maximum genus, embedding, graph, greedy algorithm}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.21
Online Dominating Set

Authors: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper is devoted to the online dominating set problem and its variants on trees, bipartite, bounded-degree, planar, and general graphs, distinguishing between connected and not necessarily connected graphs. We believe this paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. In most cases, we obtain tight bounds on the competitive ratios. Our results show that requiring the graphs to be presented in a connected fashion allows the online algorithms to obtain provably better solutions. Furthermore, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage.
Cite as

Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcik, and Kim S. Larsen. Online Dominating Set. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2016.21,
  author =	{Boyar, Joan and Eidenbenz, Stephan J. and Favrholdt, Lene M. and Kotrbcik, Michal and Larsen, Kim S.},
  title =	{{Online Dominating Set}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.21},
  URN =		{urn:nbn:de:0030-drops-60434},
  doi =		{10.4230/LIPIcs.SWAT.2016.21},
  annote =	{Keywords: online algorithms, dominating set, competitive analysis, graph classes, connected graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact