Výsledky vyhledávání - "Marcin Pilipczuk"

Akademický článek

Autor: Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory (2022)

A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and th

Externí odkaz: https://doaj.org/article/3087e4fd424c4c00970f58434b1ea0f0

Zobrazit plný text záznamu

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

Autor: Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Fedor V. Fomin, Marcin Pilipczuk, Dániel Marx

Publikováno v: FOCS

We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e28b4032f1abc99174e82c6ff0e8e487
https://doi.org/10.1137/19m1262504

Zobrazit plný text záznamu

The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs

Autor: Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge

Publikováno v: Algorithmica. 85:1202-1250

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecut

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c23ec01c30be4d9af35f0993782f8c96
https://doi.org/10.1007/s00453-022-01064-1

Zobrazit plný text záznamu

Akademický článek

Two lower bounds for $p$-centered colorings

Autor: Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, François Pitois

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 4, Iss Graph Theory (2020)

Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is \emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion

Externí odkaz: https://doaj.org/article/e8bebe963e844d69aec12471b1824778

Zobrazit plný text záznamu

Akademický článek

A Double Exponential Lower Bound for the Distinct Vectors Problem

Autor: Marcin Pilipczuk, Manuel Sorge

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 4, Iss Discrete Algorithms (2020)

In the (binary) Distinct Vectors problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et

Externí odkaz: https://doaj.org/article/b44b0772f988431dad4945936d104ec7

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání