Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Grüttemeier, Niels"'
In the NP-hard Max $c$-Cut problem, one is given an undirected edge-weighted graph $G$ and aims to color the vertices of $G$ with $c$ colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $c=2$ is the
Externí odkaz:
http://arxiv.org/abs/2409.13380
Autor:
Balzereit, Kaja, Grüttemeier, Niels, Morawietz, Nils, Reinhardt, Dennis, Windmann, Stefan, Wolf, Petra
In this work, we study the task of scheduling jobs on a single machine with sequence dependent family setup times under the goal of minimizing the makespan, that is, the completion time of the last job in the schedule. This notoriously NP-hard proble
Externí odkaz:
http://arxiv.org/abs/2409.00771
Cyber-physical production systems consist of highly specialized software and hardware components. Most components and communication protocols are not built according to the Secure by Design principle. Therefore, their resilience to cyberattacks is li
Externí odkaz:
http://arxiv.org/abs/2406.10287
In the Vertex Triangle 2-Club problem, we are given an undirected graph $G$ and aim to find a maximum-vertex subgraph of $G$ that has diameter at most 2 and in which every vertex is contained in at least $\ell$ triangles in the subgraph. So far, the
Externí odkaz:
http://arxiv.org/abs/2211.01701
In Bayesian Network Structure Learning (BNSL), one is given a variable set and parent scores for each variable and aims to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Ev
Externí odkaz:
http://arxiv.org/abs/2204.02902
We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedul
Externí odkaz:
http://arxiv.org/abs/2203.07401
We introduce and study Weighted Min $(s,t)$-Cut Prevention, where we are given a graph $G=(V,E)$ with vertices $s$ and $t$ and an edge cost function and the aim is to choose an edge set $D$ of total cost at most $d$ such that $G$ has no $(s,t)$-edge
Externí odkaz:
http://arxiv.org/abs/2107.04482
A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. \textsc{Polytree Lear
Externí odkaz:
http://arxiv.org/abs/2105.09675
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:1, Graph Theory (March 3, 2023) dmtcs:7636
We study the computational complexity of $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion. In these problems, one is given a $c$-edge-colored graph and wants to destroy all induced $c$-colored paths or cycles, respectively, on $\ell$ v
Externí odkaz:
http://arxiv.org/abs/2104.03138
Publikováno v:
Journal of Artificial Intelligence Research (JAIR), 74:1225-1267, 2022
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close
Externí odkaz:
http://arxiv.org/abs/2004.14724