اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA new record of graph enumeration enabled by parallel processing
83
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering serval optimal regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers strengths of using thousands of processor cores.
قيم البحث
اقرأ أيضاً
Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing dep
th of a function describes how many canalizing variables can be recursively picked off, until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs $G$ and $H$, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph
isomorphism (ListIso) is NP-complete: for each $u in V(G)$, we are given a list ${mathfrak L}(u) subseteq V(H)$ of possible images of $u$. After 35 years, we revive the study of this problem and consider which results for GraphIso translate to ListIso. We prove the following: 1) When GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso. 2) Combinatorial algorithms for GraphIso translate into algorithms for ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs, and bounded treewidth graphs. 3) Algorithms based on group theory do not translate: ListIso remains NP-complete for cubic colored graphs with sizes of color classes bounded by 8. Also, ListIso allows to classify results for the graph isomorphism problem. Some algorithms are robust and translate to ListIso. A fundamental problem is to construct a combinatorial polynomial-time algorithm for cubic graph isomorphism, avoiding group theory. By the 3rd result, ListIso is NP-hard for them, so no robust algorithm for cubic graph isomorphism exists, unless P = NP.
We present several enumeration results holding in sets of words called neutral and which satisfy restrictive conditions on the set of possible extensions of nonempty words. These formulae concern return words and bifix codes. They generalize formulae
previously known for Sturmian sets or more generally for tree sets. We also give a geometric example of this class of sets, namely the natural coding of some interval exchange transformations.
The shift-enabled property of an underlying graph is essential in designing distributed filters. This article discusses when a random graph is shift-enabled. In particular, popular graph models ER, WS, BA random graph are used, weighted and unweighte
d, as well as signed graphs. Our results show that the considered unweighted connected random graphs are shift-enabled with high probability when the number of edges is moderately high. However, very dense graphs, as well as fully connected graphs, are not shift-enabled. Interestingly, this behaviour is not observed for weighted connected graphs, which are always shift-enabled unless the number of edges in the graph is very low.
We are given an integer $d$, a graph $G=(V,E)$, and a uniformly random embedding $f : V rightarrow {0,1}^d$ of the vertices. We are interested in the probability that $G$ can be realized by a scaled Euclidean norm on $mathbb{R}^d$, in the sense that
there exists a non-negative scaling $w in mathbb{R}^d$ and a real threshold $theta > 0$ so that [ (u,v) in E qquad text{if and only if} qquad Vert f(u) - f(v) Vert_w^2 < theta,, ] where $| x |_w^2 = sum_i w_i x_i^2$. These constraints are similar to those found in the Euclidean minimum spanning tree (EMST) realization problem. A crucial difference is that the realization map is (partially) determined by the random variable $f$. In this paper, we consider embeddings $f : V rightarrow { x, y}^d$ for arbitrary $x, y in mathbb{R}$. We prove that arbitrary trees can be realized with high probability when $d = Omega(n log n)$. We prove an analogous result for graphs parametrized by the arboricity: specifically, we show that an arbitrary graph $G$ with arboricity $a$ can be realized with high probability when $d = Omega(n a^2 log n)$. Additionally, if $r$ is the minimum effective resistance of the edges, $G$ can be realized with high probability when $d=Omegaleft((n/r^2)log nright)$. Next, we show that it is necessary to have $d geq binom{n}{2}/6$ to realize random graphs, or $d geq n/2$ to realize random spanning trees of the complete graph. This is true even if we permit an arbitrary embedding $f : V rightarrow { x, y}^d$ for any $x, y in mathbb{R}$ or negative weights. Along the way, we prove a probabilistic analog of Radons theorem for convex sets in ${0,1}^d$. Our tree-realization result can complement existing results on statistical inference for gene expression data which involves realizing a tree, such as [GJP15].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
