Zobrazeno 1 - 10
of 28
pro vyhledávání: '"Schepper, Philipp"'
For the vertex selection problem $(\sigma,\rho)$-DomSet one is given two fixed sets $\sigma$ and $\rho$ of integers and the task is to decide whether we can select vertices of the input graph, such that, for every selected vertex, the number of selec
Externí odkaz:
http://arxiv.org/abs/2403.07524
Autor:
Focke, Jacob, Frei, Fabian, Li, Shaohua, Marx, Dániel, Schepper, Philipp, Sharma, Roohani, Węgrzycki, Karol
We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitPack asks: Can removing k (deletable) vertices of a graph G prevent us
Externí odkaz:
http://arxiv.org/abs/2402.14927
Autor:
Focke, Jacob, Marx, Dániel, Inerney, Fionn Mc, Neuen, Daniel, Sankar, Govind S., Schepper, Philipp, Wellnitz, Philip
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets $\sigma,\rho$ of non-negative integers, a $(\sigma,\rho)$-set of a graph $G$ is a set $S$ of
Externí odkaz:
http://arxiv.org/abs/2306.03640
Autor:
Focke, Jacob, Marx, Dániel, Inerney, Fionn Mc, Neuen, Daniel, Sankar, Govind S., Schepper, Philipp, Wellnitz, Philip
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets $\sigma,\rho$ of non-negative integers, a $(\sigma,\rho)$-set of a graph $G$ is a set $S$ of vertices such that $|N(u
Externí odkaz:
http://arxiv.org/abs/2211.04278
In this paper, we consider a general notion of convolution. Let $D$ be a finite domain and let $D^n$ be the set of $n$-length vectors (tuples) of $D$. Let $f : D \times D \to D$ be a function and let $\oplus_f$ be a coordinate-wise application of $f$
Externí odkaz:
http://arxiv.org/abs/2209.01623
The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameterization by the leafage of classical domination and cut problems on cho
Externí odkaz:
http://arxiv.org/abs/2208.02850
The Edge Multicut problem is a classical cut problem where given an undirected graph $G$, a set of pairs of vertices $\mathcal{P}$, and a budget $k$, the goal is to determine if there is a set $S$ of at most $k$ edges such that for each $(s,t) \in \m
Externí odkaz:
http://arxiv.org/abs/2205.10105
In the general AntiFactor problem, a graph $G$ is given with a set $X_v\subseteq \mathbb{N}$ of forbidden degrees for every vertex $v$ and the task is to find a set $S$ of edges such that the degree of $v$ in $S$ is not in the set $X_v$. Standard tec
Externí odkaz:
http://arxiv.org/abs/2110.09369
For the General Factor problem we are given an undirected graph $G$ and for each vertex $v\in V(G)$ a finite set $B_v$ of non-negative integers. The task is to decide if there is a subset $S\subseteq E(G)$ such that $deg_S(v)\in B_v$ for all vertices
Externí odkaz:
http://arxiv.org/abs/2105.08980
Many problems in interprocedural program analysis can be modeled as the context-free language (CFL) reachability problem on graphs and can be solved in cubic time. Despite years of efforts, there are no known truly sub-cubic algorithms for this probl
Externí odkaz:
http://arxiv.org/abs/2102.13095