亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set $V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed \emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$, and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set for short) if no two vertices in $G$ have the same set of neighbors in $S$, and each vertex in $S$ is open-dominated exactly once by $S$. The problem of deciding whether or not $G$ has an $OLD_{oind}$-set has important applications that have been reported elsewhere. As the problem is known to be $\mathcal{NP}$-complete, it appears to be notoriously difficult as we show that its complexity remains the same even for just planar bipartite graphs of maximum degree five and girth six, and also for planar subcubic graphs of girth nine. Also, we present characterizations of both $P_4$-tidy graphs and the complementary prisms of cographs that have an $OLD_{oind}$-set.

In this paper, some preliminaries about signal flow graph, linear time-invariant system on F(z) and computational complexity are first introduced in detail. In order to synthesize the necessary and sufficient condition on F(z) for a general 2-path problem, the sufficient condition on F(z) or R and necessary conditions on F(z) for a general 2-path problem are secondly analyzed respectively. Moreover, an equivalent sufficient and necessary condition on R whether there exists a general 2-path is deduced in detail. Finally, the computational complexity of the algorithm for this equivalent sufficient and necessary condition is introduced so that it means that the general 2-path problem is a P problem.

A family of sets is $(p,q)$-intersecting if every nonempty subfamily of $p$ or fewer sets has at least $q$ elements in its total intersection. A family of sets has the $(p,q)$-Helly property if every nonempty $(p,q)$-intersecting subfamily has total intersection of cardinality at least $q$. The $(2,1)$-Helly property is the usual Helly property. A hypergraph is $(p,q)$-Helly if its edge family has the $(p,q)$-Helly property and hereditary $(p,q)$-Helly if each of its subhypergraphs has the $(p,q)$-Helly property. A graph is $(p,q)$-clique-Helly if the family of its maximal cliques has the $(p,q)$-the Helly property and hereditary $(p,q)$-clique-Helly if each of its induced subgraphs is $(p,q)$-clique-Helly. The classes of $(p,q)$-biclique-Helly and hereditary $(p,q)$-biclique-Helly graphs are defined analogously. We prove several characterizations of hereditary $(p,q)$-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. We give an improved time bound for the recognition of $(p,q)$-Helly hypergraphs for each fixed $q$ and show that the recognition of hereditary $(p,q)$-Helly hypergraphs can be solved in polynomial time if $p$ and $q$ are fixed but co-NP-complete if $p$ is part of the input. In addition, we generalize to $(p,q)$-clique-Helly graphs the characterization of $p$-clique-Helly graphs in terms of expansions and give different characterizations of hereditary $(p,q)$-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of $(p,q)$-clique-Helly graphs and prove that the recognition problem of hereditary $(p,q)$-clique-Helly graphs is polynomial-time solvable for $p$ and $q$ fixed but NP-hard if $p$ or $q$ is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (hereditary) $(p,q)$-biclique-Helly graphs.

The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. The players are edges, and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for computing the nucleolus when the core is not empty. In order to compute the nucleolus in the core, we introduce the prime partition which is built on the densest subgraph lattice. The prime partition decomposes the edge set of a graph into a partially ordered set defined from minimal densest minors and their invariant precedence relation. Moreover, edges from the same partition always have the same value in a core allocation. Consequently, when the core is not empty, the prime partition significantly reduces the number of variables and constraints required in the linear programs of Maschler's scheme and allows us to compute the nucleolus in polynomial time. Besides, the prime partition provides a graph decomposition analogous to the celebrated core decomposition and the density-friendly decomposition, which may be of independent interest.

We prove a bound of $O( k (n+m)\log^{d-1})$ on the number of incidences between $n$ points and $m$ axis parallel boxes in $\mathbb{R}^d$, if no $k$ boxes contain $k$ common points. That is, the incidence graph between the points and the boxes does not contain $K_{k,k}$ as a subgraph. This new bound improves over previous work by a factor of $\log^d n$, for $d >2$. We also study other variants of the problem. For halfspaces, using shallow cuttings, we get a near linear bound in two and three dimensions. Finally, we present near linear bound for the case of shapes in the plane with low union complexity (e.g. fat triangles).

The median of a graph $G$ with weighted vertices is the set of all vertices $x$ minimizing the sum of weighted distances from $x$ to the vertices of $G$. For any integer $p\ge 2$, we characterize the graphs in which, with respect to any non-negative weights, median sets always induce connected subgraphs in the $p$th power $G^p$ of $G$. This extends some characterizations of graphs with connected medians (case $p=1$) provided by Bandelt and Chepoi (2002). The characteristic conditions can be tested in polynomial time for any $p$. We also show that several important classes of graphs in metric graph theory, including bridged graphs (and thus chordal graphs), graphs with convex balls, bucolic graphs, and bipartite absolute retracts, have $G^2$-connected medians. Extending the result of Bandelt and Chepoi that basis graphs of matroids are graphs with connected medians, we characterize the isometric subgraphs of Johnson graphs and of halved-cubes with connected medians.

Learning mapping between two function spaces has attracted considerable research attention. However, learning the solution operator of partial differential equations (PDEs) remains a challenge in scientific computing. Therefore, in this study, we propose a novel pseudo-differential integral operator (PDIO) inspired by a pseudo-differential operator, which is a generalization of a differential operator and characterized by a certain symbol. We parameterize the symbol by using a neural network and show that the neural-network-based symbol is contained in a smooth symbol class. Subsequently, we prove that the PDIO is a bounded linear operator, and thus is continuous in the Sobolev space. We combine the PDIO with the neural operator to develop a pseudo-differential neural operator (PDNO) to learn the nonlinear solution operator of PDEs. We experimentally validate the effectiveness of the proposed model by using Burgers' equation, Darcy flow, and the Navier-Stokes equation. The results reveal that the proposed PDNO outperforms the existing neural operator approaches in most experiments.

We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $\chi'_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every integer $d$, every multigraph $G$ with maximum degree $\Delta$ is $(\lceil \frac{\Delta}{d} \rceil, d)$-edge colourable if $d$ is even and $(\lceil \frac{3\Delta - 1}{3d - 1} \rceil, d)$-edge colourable if $d$ is odd and these bounds are tight. We also prove that for every simple graph $G$, $\chi'_{d}(G) \in \{ \lceil \frac{\Delta}{d} \rceil, \lceil \frac{\Delta+1}{d} \rceil \}$ and characterize the values of $d$ and $\Delta$ for which it is NP-complete to compute $\chi'_d(G)$. These results generalize several classic results on the chromatic index of a graph by Shannon, Vizing, Holyer, Leven and Galil.

The boundary operator is a linear operator that acts on a collection of high-dimensional binary points (simplices) and maps them to their boundaries. This boundary map is one of the key components in numerous applications, including differential equations, machine learning, computational geometry, machine vision and control systems. We consider the problem of representing the full boundary operator on a quantum computer. We first prove that the boundary operator has a special structure in the form of a complete sum of fermionic creation and annihilation operators. We then use the fact that these operators pairwise anticommute to produce an $\mathcal{O}(n)$-depth circuit that exactly implements the boundary operator without any Trotterization or Taylor series approximation errors. Having fewer errors reduces the number of shots required to obtain desired accuracies.

Graph Neural Networks (GNN) come in many flavors, but should always be either invariant (permutation of the nodes of the input graph does not affect the output) or equivariant (permutation of the input permutes the output). In this paper, we consider a specific class of invariant and equivariant networks, for which we prove new universality theorems. More precisely, we consider networks with a single hidden layer, obtained by summing channels formed by applying an equivariant linear operator, a pointwise non-linearity and either an invariant or equivariant linear operator. Recently, Maron et al. (2019) showed that by allowing higher-order tensorization inside the network, universal invariant GNNs can be obtained. As a first contribution, we propose an alternative proof of this result, which relies on the Stone-Weierstrass theorem for algebra of real-valued functions. Our main contribution is then an extension of this result to the equivariant case, which appears in many practical applications but has been less studied from a theoretical point of view. The proof relies on a new generalized Stone-Weierstrass theorem for algebra of equivariant functions, which is of independent interest. Finally, unlike many previous settings that consider a fixed number of nodes, our results show that a GNN defined by a single set of parameters can approximate uniformly well a function defined on graphs of varying size.