Search

We consider the shortest path problem on graphs with weights taking values in Cartesian products of cost monoids. Such cost structures appear in multiobjective planning including, for instance, the minimum-violation planning framework. It is known that these products often do not satisfy the conditions of a cost monoid. Classical dynamic programming graph search algorithms may therefore fail to find an optimal solution.

Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of k colors to the vertices of G such that every vertex contains vertices of all k colors in its neighborhood. The coupon chromatic number of G, denoted \(\chi _c (G)\), is the maximum k for which a k-coupon coloring exists. In this paper, we present an upper bound for the coupon chromatic number of Cartesian product of graphs G and H in terms of |V(G)| and |V(H)|. Further, we prove that if G and H are bipartite graphs then \(G\square H\) has a coupon coloring with \(2\min \{\chi _c(G),\chi _c(H)\}\) colors. As consequences, for any positive integer n, we obtain the coupon chromatic number and total domination number of n-dimensional torus \(\mathop {\square }\limits _{i=1}^{n} C_{k_i}\) with some suitable conditions to each \(k_i\), which turns out to be a generalization of the result due to S. Gravier [Total domination number of grid graphs, Discrete Appl. Math. 121 (2002) 119–128]. Finally, for any \(r\ge 0, d\ge 2\), we obtain the coupon coloring for the Hamming graph \(K_d\square K_d\square \cdots \square K_d\) (\(2^r\) times).

We define and study the notion of an indexed frame. This is a bi-dimensional structure consisting of a Cartesian product equipped with relations which only relate pairs if they coincide in one of their components. We show that these structures are quite ubiquitous in modal logic, showing up in the literature as products of Kripke frames, subset spaces, or temporal frames for STIT logics. We show that indexed frames are completely characterised by their ‘orthogonal’ relations, and we provide their sound and complete logic. Using these ‘orthogonality’ results, we provide necessary and sufficient conditions for an arbitrary Kripke frame to be isomorphic to certain well-known bi-dimensional structures.

Induced subgraph isomorphism search finds the occurrences of embedded subgraphs within a single large data graph that are strictly isomorphic to a given query graph. Labeled graphs contain object types and are a primary input source to this core search problem, which applies to systems like graph databases for answering queries. In recent years, researchers have employed GPU parallel solutions to this problem to help accelerate runtimes by utilizing the filtering-and-joining framework, which first filters vertices that cannot be part of the solution then joins partial solutions with candidate edges until full isomorphisms are determined. However, the performance of current GPU-based solutions is hindered by limited filtering effectiveness and presence of extraneous computations. This paper presents G-Morph, a fast GPU-based induced subgraph isomorphism search system for labeled graphs. Our filtering-and-joining system parallelizes both phases by upfront eliminating irrelevant vertices via a novel space-efficient vertex signature hashing strategy and efficiently joining partial solutions through use of a novel sliding window algorithm (slide-join) that provides overflow protection for larger input. Together these techniques greatly reduce extraneous computations by reducing Cartesian products and improving edge verification while supporting large scan operations (split-scan). G-Morph outperforms the state-of-the-art GPU-based GSI and CPU-based VF3 systems on labeled real-world graphs achieving speedups of up to 15.78\(\times \) and 43.56\(\times \) respectively.

The layout of the processors and links are represented a network structure in a distributed computer system. A graph is regarded as the topological structure of an interconnection network as usual, vertices and edges stand for processors and links between them, respectively. The internally disjoint Steiner trees of graphs are used in information engineering design and telecommunication networks. The \(\ell \)-set tree connectivity (also is called generalized \(\ell \)-connectivity), as an extension of the traditional connectivity, can provide for measuring the capability of connection arbitrary \(\ell \) vertices in a network. The folded Petersen cube networks \(FPQ_{n,k}\) have good properties and can be modeled the topological structure of a massively parallel processing system. This article shows the 3-set tree connectivity of \(FPQ_{n,k}\) is \(n+3k-1\).

Optimal bounds for the uniform errors of approximation and quadrature in the Sinc basis are extended from simple cartesian products to a class of polyhedra sufficient for most applications by complexification of the space of a simplicial complex. The complexification admits approximation of functions defined on realizations of simplicial complexes that have holomorphic extensions and on which area measure has a holomorphic representation.

The \(\varDelta \)-interval of \(u,v \in V (G)\), \(I_{\varDelta }(u,v)\), is the set formed by u, v and every w in V(G) such that \(\{u, v, w\}\) is a triangle \((K_3)\) of G. A set S of vertices such that \(I_{\varDelta } (S)=V(G)\) is called a \(\varDelta \)-set. \(\varDelta \)-number is the minimum cardinality of a \(\varDelta \)-set. \(\varDelta \)-graph is a graph with all the vertices lie on some triangles. If a block graph is a \(\varDelta \)-graph, then we say that it is a block \(\varDelta \)-graph. A set \(S\subseteq V (G)\) is \(\varDelta \)-convex if there is no vertex \(u \in V(G)\setminus S\) forming a triangle with two vertices of S. The convexity number of a graph G with respect to the \(\varDelta \)-convexity is the maximum cardinality of a proper convex subset of G. We have given an exact value for the convexity number of block \(\varDelta \)-graphs with diameter \({\le }3\), block \(\varDelta \)-graphs with diameter \({>}3\) and the two standard graph products (Strong, Lexicographic products), a bound for Cartesian product. Also discussed some bounds for \(\varDelta \)-number and a realization is done for the \(\varDelta \)-number and the hull number.

In this paper, we propose FastThetaJoin, an optimization technique for \(\theta \)-join operation on multi-way data streams, which is an essential query often used in many data analytical tasks. The \(\theta \)-join operation on multi-way data streams is notoriously difficult as it always involves tremendous shuffle cost due to data movements between multiple operation components, rendering it hard to be efficiently implemented in a distributed environment. As with previous methods, FastThetaJoin also tries to minimize the number of \(\theta \)-joins, but it is distinct from others in terms of making partitions, deleting unnecessary data items, and performing the Cartesian product. FastThetaJoin not only effectively minimizes the number of \(\theta \)-joins, but also substantially improves the efficiency of its operations in a distributed environment. We implemented FastThetaJoin in the framework of Spark Streaming, characterized by its efficient bucket implementation of parameterized windows. The experimental results show that, compared with the existing solutions, our proposed method can speed up the \(\theta \)-join processing while reducing its overhead; the specific effects of the optimization is correlated to the nature of data streams–the greater the data difference is, the more apparent the optimization effect is.

We show that any set with small Wiener norm has small multiplicative energy. It gives some new bounds for Wiener norm for sets with small product set. Also, we prove that any symmetric subset S of an abelian group has a nonzero Fourier coefficient of size Ω(|S|1∕3).

Large NFAs are automata that cannot fit in a single computer, or the computations would not fit within the computer RAM, or may take a long time. We describe and implement a BSP solution of such large NFAs intersection. Our method avoids producing unreachable states of the product automaton, contrary to previous solutions. These solutions, based on MapReduce for instance, process all the Cartesian product of inputs NFAs. A running example is provided with execution details. Finally, complexity analysis is given. This work will help in bringing out relevant programming artifacts for our long term goal that consists of a high level distributed graph language.

In “Pure Mathematics” a statement like x ∈ X is either true or false, in formal terms: it has a truth value, “yes” or “no”, in numerical terms: tv(x ∈ X) ∈ L = {0, 1}. But in “Applied Mathematics” multivalued parameters are used. For example, if a given refrigerant is ecologically worthwhile may be answered by its values of ODP (ozone depletion potential), GWP (general warming potential) and ALT (atmospheric lifetime), i.e. by a triple of real numbers. Let us call such answers evaluations. They are elements of a lattice L, in this particular case of L = [0, 1]3, if the parameters are normalized. And we can consider such evaluations as L-subsets (see below) of the cartesian product O × A of the set O of objects and the set A of attributes. The crucial point is that this allows a choice of a suitable set theory together with the corresponding logic, in a problem-orientable way, since we can use a more or a less strict argumentation.

A graph G is said to be k-distinguishable if every vertex of the graph can be colored from a set of k colors such that no non-trivial automorphism fixes every color class. The distinguishing number D(G) is the least integer k for which G is k-distinguishable. If for each \(v\in V(G)\) we have a list L(v) of colors, and we stipulate that the color assigned to vertex v comes from its list L(v) then G is said to be \(\mathcal {L}\)-distinguishable where \(\mathcal {L}=\{L(v)\}_{v\in V(G)}\). The list distinguishing number of a graph, denoted \(D_l(G)\), is the minimum integer k such that every collection of lists \(\mathcal {L}\) with \(|L(v)|=k\) admits an \(\mathcal {L}\)-distinguishing coloring. In this paper, we prove that when a connected graph G is prime with respect to the Cartesian product then \(D_l(G^r) = D(G^r)\) for \(r \ge 3\) where \(G^r\) is the Cartesian product of the graph G taken r times. The \(p^{th}\) power of a graph (Some authors use \(G^p\) to denote the pth power of G, to avoid confusion with the notation of Cartesian power of graph G we use \(G^{[p]}\) for the pth power of G.) G is the graph \(G^{[p]}\), whose vertex set is V(G) and in which two vertices are adjacent when they have distance less than or equal to p. We determine \(D_l(Q_n^{[p]})\) for all \(n \ge 7, p \ge 1\), where \(Q_n=K_2^n\) is the hypercube of dimension n.

Recently, GANs have become popular for synthesizing photorealistic facial images with desired facial attributes. However, crucial to the success of such networks is the availability of large-scale datasets that are fully-attributed, i.e., datasets in which the Cartesian product of all attribute values is present, as otherwise the learning becomes skewed. Such fully-attributed datasets are impractically expensive to collect. Many existing datasets are only partially-attributed, and do not have any subjects in common. It thus becomes important to be able to jointly learn from such datasets. In this paper, we propose a GAN-based facial image generator that can be trained on partially-attributed disjoint datasets. The key idea is to use a smaller, fully-attributed dataset to bridge the learning. Our generator (i) provides independent control of multiple attributes, and (ii) renders photorealistic facial images with target attributes.

An equalized incomplete tournament EIT(p, r) on p teams which are ranked from 1 to p, is a tournament in which every team plays against r teams and the total strength of the opponents that every team plays with is a constant. A handicap incomplete tournament HIT(p, r) on p teams is a tournament in which every team plays against r opponents in such a way that

We study an injective embedding of p-adic integers in the Cartesian product of p copies of sets of 2-adic integers. This embedding allows to explicitly specify any p-adic integer through p specially selected 2-adic numbers. This representation can be used in p-adic mathematical physics, for example, in justifying choice of the parameter p.

This article is devoted to present the first status connectivity indices and its coindices of some composite graphs such as join, Cartesian product, corona product, and composition of two given connected graphs.

This paper considers the one-cop-moves game played on a graph. In this game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. The goal of the cops is to capture the robber. At cops’ turns, exactly one cop is allowed to move from his location to an adjacent vertex; at robber’s turns, she is allowed to move from her location to an adjacent vertex or to stay still. We want to find the minimum number of cops to capture the robber. This number is known as the cop number. In this paper, we investigate the cop number of several classes of graphs, including graphs with treewidth at most 2, Halin graphs, and Cartesian product graphs. We also give a characterization of k-winnable graphs in the one-cop-moves game.

The Laplacian energy of an intuitionistic fuzzy graph concept is extended to dominating Laplacian energy in various products of intuitionistic fuzzy graph. In this paper, we have obtained the value of dominating Laplacian energy in two products such as Cartesian product and tensor product. Also we study the relation between the dominating Laplacian energy in the products in two intuitionistic fuzzy graphs.

A radio labeling of a graph G is a mapping \(\varphi : V(G) \rightarrow \{0, 1, 2,\ldots \}\) such that \(|\varphi (u)-\varphi (v)|\ge \mathrm{diam}(G) + 1 - d(u,v)\) for every pair of distinct vertices u, v of G, where \(\mathrm{diam}(G)\) and d(u, v) are the diameter of G and distance between u and v in G, respectively. The radio number \(\mathrm{rn}(G)\) of G is the smallest number k such that G has radio labeling with \(\max \{\varphi (v):v \in V(G)\} = k\). In this paper, we slightly improve the lower bound for the radio number of graphs given by Das et al. in [5] and, give necessary and sufficient condition to achieve the lower bound. Using this result, we determine the radio number for cartesian product of paths \(P_{n}\) and the Peterson graph P. We give a short proof for the radio number of cartesian product of paths \(P_{n}\) and complete graphs \(K_{m}\) given by Kim et al. in [6].

Given a finite collection of disjointness preserving linear operators with values in an f-algebra, the mapping defined as their pointwise product is a disjointness preserving multilinear operator. The central result asserts that an arbitrary order bounded disjointness preserving multilinear operator from the Cartesian product of vector lattices into an arbitrary vector lattice has a similar structure. Using this fact, we establish a multilinear version of the Hart theorem on the associated lattice homomorphism, and also give some consequences on the structure of disjointness preserving homogeneous polynomials.

Beyond mean and variance, traditionally used in stochastic approaches, the full one-point one-time concentration probability density function (PDF) is needed to estimate exceedance probabilities in assessments of groundwater contamination. By solving PDF evolution equations one avoids the cumbersome MC simulations used to obtain statistical inferences. The PDF approach is mainly useful in case of reactive transport: because reaction terms are in a closed form, there is no need to upscale them, as in case of modeling the mean behavior of species concentrations. In a filtered density function (FDF) approach, the PDF is estimated by spatial filtering. PDF/FDF equations will be formulated as Fokker–Planck equations with solutions in the Cartesian product of physical and concentration spaces. Numerical solutions will be obtained by GRW algorithms.

This chapter treats two interrelated topics in discrete mathematics: elementary Set Theory (set notation; subsets, partitions, and power sets; and unions, intersections, set differences, and Cartesian products) and the theory of Combinatorics (sequential counting, permutations, and combinations). Strong connections to Propositional Logic (Chapter 1) are demonstrated, and applications are made to binomial expansion, discrete probability, and everyday counting. The material on Set Theory also provides the theoretical foundation for topics later in the text on infinite sets (Chapter 5), functions (Chapter 6), and relations (Chapters 6 and 7).

We present a general two-side market model with divisible commodities and price functions of participants. A general existence result on unbounded sets is obtained from its variational inequality reformulation. We describe an extension of the network flow equilibrium problem with elastic demands and a new equilibrium type model for resource allocation problems in wireless communication networks, which appear to be particular cases of the general market model. This enables us to obtain new existence results for these models as some adjustments of that for the market model. Under certain additional conditions, the general market model can be reduced to a decomposable optimization problem where the goal function is the sum of two functions and one of them is convex separable, whereas the feasible set is the corresponding Cartesian product. We discuss some versions of the partial linearization method, which can be applied to these network equilibrium problems.

A binary relation, which connects elements of a set \( {\mathbb{X}} \) with elements of a set \( {\mathbb{Y}} \), is any subset of the Cartesian product \( {\mathbb{X}} \times {\mathbb{Y}} \).

The method of a physical swarm modeling, based on application of semi-Markov process theory to description of swarm unit cyclograms is worked out. It is shown, that ordinary semi-Markov processes with structural states are abstract analogue of units cyclograms. The method of gathering of ordinary semi-Markov processes into M-parallel process and further transformation of it into complex semi-Markov process with functional states is proposed. It is shown that functional states may be obtained as Cartesian product of sets of ordinary semi-Markov processes states. Operation of semi-Markov matrices Cartesian product is introduced. Method of evaluation of elements of complex semi-Markov matrix is worked out.

The previous chapter has provided various examples of multidimensional MCs that are used to model systems composed of a finite number of interacting submodels. Assuming that there are H such interacting submodels, the state space of submodel h was denoted by \(\mathcal{S}^{(h)}\) with \(\mathcal{S}^{(h)} \subseteq \mathbb{Z}_{\geq 0}\) for h = 1, …, H, and \(\mathcal{S} = \times _{h=1}^{H}\mathcal{S}^{(h)}\) represented the Cartesian product of the submodel state spaces. Because the Cartesian product of multiple submodel state spaces is used in its definition without any restriction on the state spaces themselves, \(\mathcal{S}\) is called the H-dimensional product state space of the model.

\(\{log\}\) (‘setlog’) is a constraint logic programming framework endowed with a decision procedure for a fragment of the language of finite sets and binary relations. As such, it can decide the satisfiability of a large class of formulas involving classic set and relational operators such as union, domain, and composition. In this paper we first extend \(\{log\}\) with the converse and identity operators in such a way that now the language of finite (set) relation algebra is fully supported. As a second improvement, Cartesian products are implemented as first-class entities which renders the solver more efficient. Finally we demonstrate the applicability of \(\{log\}\) by conducting an extensive empirical evaluation over 1,300 problems, most of them extracted from the TPTP library.