Zobrazeno 1 - 10
of 70
pro vyhledávání: '"Rauch Johannes"'
Autor:
Rauch, Johannes
We describe the implementation of the exact solver weberknecht and the heuristic solver weberknecht_h for the One-Sided Crossing Minimization problem.
Externí odkaz:
http://arxiv.org/abs/2412.06361
Autor:
Rauch, Johannes, Rautenbach, Dieter
Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph $G$ with $n$ vertices and at most $2n-4$ edges has a stable cutset, which is a stable set of vertices whose removal disconnects the graph. Le and Pfender showed that
Externí odkaz:
http://arxiv.org/abs/2412.00337
We propose the conjecture that every graph $G$ of order $n$ with less than $3n-6$ edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts and show that the density condition would be best possible. We verify t
Externí odkaz:
http://arxiv.org/abs/2409.17724
One way to define the Matching Cut problem is: Given a graph $G$, is there an edge-cut $M$ of $G$ such that $M$ is an independent set in the line graph of $G$? We propose the more general Conflict-Free Cut problem: Together with the graph $G$, we are
Externí odkaz:
http://arxiv.org/abs/2311.01077
The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is $\textsf{NP}$-complete even when the input graph is planar and has maximum degree five. In this paper, we
Externí odkaz:
http://arxiv.org/abs/2307.02107
We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this resul
Externí odkaz:
http://arxiv.org/abs/2304.10353
Publikováno v:
In Journal of Computer and System Sciences March 2025 148
Autor:
Rauch, Johannes, Rautenbach, Dieter
The annihilation number $a(G)$ of a graph $G$ is an efficiently computable upper bound on the independence number $\alpha(G)$ of $G$. Recently, Hiller observed that a characterization of the graphs $G$ with $\alpha(G)=a(G)$ due to Larson and Pepper i
Externí odkaz:
http://arxiv.org/abs/2204.11094
Autor:
Bilka, Tadeas, Braun, Nils, Hauth, Thomas, Kuhr, Thomas, Lavezzi, Lia, Metzner, Felix, Paul, Stephan, Prencipe, Elisabetta, Prim, Markus, Rauch, Johannes, Ritman, James, Schlueter, Tobias, Spataro, Stefano
The GENFIT toolkit, initially developed at the Technische Universitaet Muenchen, has been extended and modified to be more general and user-friendly. The new GENFIT, called GENFIT2, provides track representation, track-fitting algorithms and graphic
Externí odkaz:
http://arxiv.org/abs/1902.04405
Autor:
Alexander, Carol, Rauch, Johannes
We develop a general multivariate aggregation property which encompasses the distinct versions of the property that were introduced by Neuberger [2012] and Bondarenko [2014] independently. This way, we classify new types of model-free realised charac
Externí odkaz:
http://arxiv.org/abs/1709.08188