Zobrazeno 1 - 10
of 138
pro vyhledávání: '"Novotna, Jana"'
Autor:
Novotna, Jana
Publikováno v:
Swahili Forum 7 (2000). 7:57-73
The aim of this article is to deal with reduplication in Swahili. In phase I, we pay attention to the process of reduplication as such, i.e., we try to define this phenomenon and we determine the scope of our study. The core of phase II is constitute
Externí odkaz:
https://ul.qucosa.de/id/qucosa%3A11551
https://ul.qucosa.de/api/qucosa%3A11551/attachment/ATT-0/
https://ul.qucosa.de/api/qucosa%3A11551/attachment/ATT-0/
Autor:
Gajarský, Jakub, Jaffke, Lars, Lima, Paloma T., Novotná, Jana, Pilipczuk, Marcin, Rzążewski, Paweł, Souza, Uéverton S.
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladde
Externí odkaz:
http://arxiv.org/abs/2205.01191
Max Weight Independent Set in graphs with no long claws: An analog of the Gy\'arf\'as' path argument
Autor:
Majewski, Konrad, Masařík, Tomáš, Novotná, Jana, Okrasa, Karolina, Pilipczuk, Marcin, Rzążewski, Paweł, Sokołowski, Marek
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomass\'{e}, SODA 2020] and provide a subexponential-time algor
Externí odkaz:
http://arxiv.org/abs/2203.04836
Publikováno v:
Proceedings: International Symposium on Algorithms and Computation, ISAAC 2022
A locally surjective homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$ that is surjective in the neighborhood of each vertex in $G$. In the list locally surjective homomorphism problem, denoted by LLSHom
Externí odkaz:
http://arxiv.org/abs/2202.12438
Autor:
Bonamy, Marthe, Bożyk, Łukasz, Grzesik, Andrzej, Hatzel, Meike, Masařík, Tomáš, Novotná, Jana, Okrasa, Karolina
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (August 14, 2022) dmtcs:7660
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, inclu
Externí odkaz:
http://arxiv.org/abs/2105.09871
Publikováno v:
SIAM Journal on Discrete Mathematics 36(2), 1416-1435, 2022
Let $\Lambda(T)$ denote the set of leaves in a tree $T$. One natural problem is to look for a spanning tree $T$ of a given graph $G$ such that $\Lambda(T)$ is as large as possible. This problem is called maximum leaf number, and it is a well-known NP
Externí odkaz:
http://arxiv.org/abs/2104.12030
Publikováno v:
Algorithmica 84(6), 1526-1547, 2022; Proceedings: Graph-Theoretic Concepts in Computer Science, WG 2021
The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $H_1,H_2,\ldots$; the graphs in the cla
Externí odkaz:
http://arxiv.org/abs/2011.06173
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $l_1$ and $l_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parame
Externí odkaz:
http://arxiv.org/abs/2010.11440
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class ${\cal G}$ if they are so on the atoms (graphs with no clique cu
Externí odkaz:
http://arxiv.org/abs/2006.03578
Publikováno v:
Algorithmica 83(12), 3649-3680 (2021)
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also be
Externí odkaz:
http://arxiv.org/abs/2002.08311