Zobrazeno 1 - 10
of 2 564
pro vyhledávání: '"parameterized algorithm"'
Autor:
Kumar, Mithilesh, Lokshtanov, Daniel
A {\em bipartite tournament} is a directed graph $T:=(A \cup B, E)$ such that every pair of vertices $(a,b), a\in A,b\in B$ are connected by an arc, and no arc connects two vertices of $A$ or two vertices of $B$. A {\em feedback vertex set} is a set
Externí odkaz:
http://arxiv.org/abs/2411.02821
Autor:
Xiong, Ziliang, Xiao, Mingyu
The Directed Feedback Vertex Set problem (DFVS) asks whether it is possible to remove at most $k$ vertices from a directed graph to make it acyclic. Whether DFVS is fixed-parameter tractable was a long-standing open problem in parameterized complexit
Externí odkaz:
http://arxiv.org/abs/2410.15411
The problem of computing vertex and edge connectivity of a graph are classical problems in algorithmic graph theory. The focus of this paper is on computing these parameters on embedded graphs. A typical example of an embedded graph is a planar graph
Externí odkaz:
http://arxiv.org/abs/2407.00586
Autor:
Korhonen, Tuukka, Sokołowski, Marek
We give an algorithm that given a graph $G$ with $n$ vertices and $m$ edges and an integer $k$, in time $O_k(n^{1+o(1)}) + O(m)$ either outputs a rank decomposition of $G$ of width at most $k$ or determines that the rankwidth of $G$ is larger than $k
Externí odkaz:
http://arxiv.org/abs/2402.12364
Autor:
Liu, Yuxi, Xiao, Mingyu
An induced subgraph is called an induced matching if each vertex is a degree-1 vertex in the subgraph. The \textsc{Almost Induced Matching} problem asks whether we can delete at most $k$ vertices from the input graph such that the remaining graph is
Externí odkaz:
http://arxiv.org/abs/2308.14116
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Ordanel, Ivy D.1 idordanel@up.edu.ph, Fernandez Jr., Proceso L.2, Juayong, Richelle Ann B.1, Clemente, Jhoirene B.1, Adorna, Henry N.1
Publikováno v:
Philippine Journal of Science. Feb2024, Vol. 153 Issue 1, p23-32. 10p.
Autor:
Eppstein, David
We prove that testing the flat foldability of an origami crease pattern (either labeled with mountain and valley folds, or unlabeled) is fixed-parameter tractable when parameterized by the ply of the flat-folded state and by the treewidth of an assoc
Externí odkaz:
http://arxiv.org/abs/2306.11939
Autor:
Korhonen, Tuukka, Lokshtanov, Daniel
We give an algorithm that takes as input an $n$-vertex graph $G$ and an integer $k$, runs in time $2^{O(k^2)} n^{O(1)}$, and outputs a tree decomposition of $G$ of width at most $k$, if such a decomposition exists. This resolves the long-standing ope
Externí odkaz:
http://arxiv.org/abs/2211.07154