Zobrazeno 1 - 10
of 144
pro vyhledávání: '"Masařík, Tomáš"'
Autor:
Balko, Martin, Hliněný, Petr, Masařík, Tomáš, Orthaber, Joachim, Vogtenhuber, Birgit, Wagner, Mirko H.
Visualizing a graph $G$ in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masa\v{r}\'ik and Hlin\v{e}n\'y [GD 2023] recently asked for each edge of $G$ to be drawn without crossings wh
Externí odkaz:
http://arxiv.org/abs/2407.21206
Autor:
Drabik, Karolina, Masařík, Tomáš
Finding a few solutions for a given problem that are diverse, as opposed to finding a single best solution to solve the problem, has recently become a notable topic in theoretical computer science. Recently, Baste, Fellows, Jaffke, Masa\v{r}\'ik, Oli
Externí odkaz:
http://arxiv.org/abs/2405.20931
We say that an edge-coloring of a graph $G$ is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of $G$ receive the same color. Furthermore, given a fixed graph $F$, we say that $G$ is rainbow $F$-saturate
Externí odkaz:
http://arxiv.org/abs/2403.15602
A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ after vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor and $K_{t,t}$ as
Externí odkaz:
http://arxiv.org/abs/2312.07962
We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a single constraint on the number of candidates that need to be selecte
Externí odkaz:
http://arxiv.org/abs/2307.06077
Autor:
Hliněný, Petr, Masařík, Tomáš
In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is useful for graph visualization. We propose investigating a property w
Externí odkaz:
http://arxiv.org/abs/2306.09550
Autor:
Gartland, Peter, Lokshtanov, Daniel, Masařík, Tomáš, Pilipczuk, Marcin, Pilipczuk, Michał, Rzążewski, Paweł
We show that the \textsc{Maximum Weight Independent Set} problem (\textsc{MWIS}) can be solved in quasi-polynomial time on $H$-free graphs (graphs excluding a fixed graph $H$ as an induced subgraph) for every $H$ whose every connected component is a
Externí odkaz:
http://arxiv.org/abs/2305.15738
Publikováno v:
Proceedings: ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
A random 2-cell embedding of a connected graph $G$ in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of faces or the genus of the corresponding 2-cell embedding becomes a rando
Externí odkaz:
http://arxiv.org/abs/2211.01032
Publikováno v:
The Electronic Journal of Combinatorics, 30(3), 36:1-36:27, 2023; Proceedings: European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB 2023
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gy\'arf\'as-Sumner conjecture is a widely-open conjecture on simple g
Externí odkaz:
http://arxiv.org/abs/2209.06171
Publikováno v:
SIAM Journal on Discrete Mathematics 38(1), 170-189, 2024
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark problem in parameterize
Externí odkaz:
http://arxiv.org/abs/2208.14841