Zobrazeno 1 - 10
of 16
pro vyhledávání: '"Zeif, Ziena"'
Autor:
Filtser, Arnold, Friedrich, Tobias, Issac, Davis, Kumar, Nikhil, Le, Hung, Mallek, Nadym, Zeif, Ziena
A $(\beta,\delta,\Delta)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $\Delta$ such that for every vertex $v\in V$, the probability that $\rm{ball}_G(v,\gamma\Delta)$ is
Externí odkaz:
http://arxiv.org/abs/2407.12230
Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wC
Externí odkaz:
http://arxiv.org/abs/2405.02378
In this paper we study the threshold model of \emph{geometric inhomogeneous random graphs} (GIRGs); a generative random graph model that is closely related to \emph{hyperbolic random graphs} (HRGs). These models have been observed to capture complex
Externí odkaz:
http://arxiv.org/abs/2306.09506
Autor:
Baguley, Samuel, Friedrich, Tobias, Neumann, Aneta, Neumann, Frank, Pappik, Marcus, Zeif, Ziena
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary
Externí odkaz:
http://arxiv.org/abs/2303.11281
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-$r$ graph, there exists a (fractional) multicommodity flow of value $f$, and a multicut of capacity $c$ s
Externí odkaz:
http://arxiv.org/abs/2211.06267
In the 1970s, Gy\H{o}ri and Lov\'{a}sz showed that for a $k$-connected $n$-vertex graph, a given set of terminal vertices $t_1, \dots, t_k$ and natural numbers $n_1, \dots, n_k$ satisfying $\sum_{i=1}^{k} n_i = n$, a connected vertex partition $S_1,
Externí odkaz:
http://arxiv.org/abs/2207.09262
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator w
Externí odkaz:
http://arxiv.org/abs/2203.08790
Autor:
Borndörfer, Ralf, Casel, Katrin, Issac, Davis, Niklanovits, Aikaterini, Schwartz, Stephan, Zeif, Ziena
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. We consider Balanced Connected Partition
Externí odkaz:
http://arxiv.org/abs/2107.04837
We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of t
Externí odkaz:
http://arxiv.org/abs/2011.04528
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-$r$ graph, there exists a (fractional) multicommodity flow of value $f$, and a multicut of capacity $c$ s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bb7643e2176f26f9132f6e597f8dd778
https://doi.org/10.1145/3564246.3585150
https://doi.org/10.1145/3564246.3585150
