Search

For a graph G and a set Z of four distinct vertices of G, a diamond on Z is a subgraph of G such that, for some labeling Z = { v 1 , v 2 , v 3 , v 4 } , there are three internally disjoint paths P 1 , P 2 , P 3 with end vertices v 1 , v 2 with v 3 , v 4 on P 1 , P 2 , respectively. Therefore, this yields a K 4 − -subdivision with branch vertices on Z. We characterize graphs G that contain no diamond on a prescribed set Z of four vertices, under the assumption that for every v ∈ Z there are three paths of G from v to Z − { v } , mutually disjoint except for v. Moreover, we can find two “different” such subdivisions, if one exists. Our proof is based on Mader's S-paths theorem.

We present a generalization of a combinatorial result by Aggarwal et al. (1989) on a linear-time algorithm that selects a constant fraction of leaves, with pairwise disjoint neighborhoods, from a binary tree embedded in the plane. This result of Aggarwal et al. (1989) is essential to the linear-time framework, which they also introduced, that computes certain Voronoi diagrams of points with a tree structure in linear time. An example is the diagram computed while updating the Voronoi diagram of points after deletion of one site. Our generalization allows that only a fraction of the tree leaves is considered, and it is motivated by research on linear time construction algorithms for Voronoi diagrams of non-point sites. We are given a plane tree T of n leaves, m of which have been marked, and each marked leaf is associated with a neighborhood (a subtree of T ) such that any two topologically consecutive marked leaves have disjoint neighborhoods. We show how to select in linear time a constant fraction of the marked leaves having pairwise disjoint neighborhoods.

Community detection is an important area of research in social media mining. Numerous algorithms have been developed to detect disjoint, overlapping, and dynamic communities in a network. However, most of the existing algorithms do not consider the influence of each node in a group, which may be different and can affect the result of community detection. In this paper, we have proposed a novel Louvain-based algorithm named “NI-Louvain,” which considers the influence of each node in a group that not only detects community but also most influential nodes in the community. The proposed algorithm works in three steps. First, the input graph is processed to reduce its density. This is done by calculating cliques from the graph. In second step, Louvain's multilevel algorithm is applied to this clique graph. The resultant community obtained has a better modularity value than the communities obtained from existing algorithms like edge betweenness, label propagation, leading eigen, Louvain, fast greedy, walktrap, and infomap. In the third step, the nodes of resultant communities are transformed back to the nodes of the original graph. This step is beneficial in detecting overlapping communities, fuzzy membership of each node, most influential node in each community formed, and outlier nodes.

An asymmetric coloring of a graph is a coloring of its vertices that is not preserved by any non-identity automorphism of the graph. The motion of a graph is the minimal degree of its automorphism group, i.e., the minimum number of elements displaced by any non-identity automorphism. In this paper we confirm Tom Tucker's "Infinite Motion Conjecture" that connected locally finite graphs with infinite motion admit an asymmetric 2-coloring. We infer this from the more general result that the inverse limit of a sequence of finite permutation groups with disjoint domains, viewed as a permutation group on the union of those domains, admits an asymmetric 2-coloring. The proof is based on the study of the interaction between epimorphisms of finite permutation groups and the structure of the setwise stabilizers of subsets of their domains., Comment: V.2 updates: Choi 1972 ref. added, Sec. 8.3 (Mathieu groups) updated, question about $M_{24}$ deleted from "Open questions." New material: New Sec. 14 added, incl. two conjectures. Minor changes made for improved clarity throughout the paper. None of the updates affects the main results or their proofs

We introduce an object called a tree growing sequence (TGS) in an effort to generalize bijective correspondences between G -parking functions, spanning trees, and the set of monomials in the Tutte polynomial of a graph G . A tree growing sequence determines an algorithm which can be applied to a single function, or to the set P G , q of G -parking functions. When the latter is chosen, the algorithm uses splitting operations – inspired by the recursive definition of the Tutte polynomial – to iteratively break P G , q into disjoint subsets. This results in bijective maps τ and ρ from P G , q to the spanning trees of G and Tutte monomials, respectively. We compare the TGS algorithm to Dhar’s algorithm and the family described by Chebikin and Pylyavskyy in 2005. Finally, we compute a Tutte polynomial of a zonotopal tiling using analogous splitting operations.

In an observational study, one is given disjoint samples of treatment units and control (untreated) units, and the goal is to compare outcomes between the two samples in order to estimate a treatment effect. A complication is that the treatment and control units often differ on important pre-treatment attributes, and these differences, referred to as covariate imbalance, can bias the estimate. One method to correct for covariate imbalance is to select a subset of the control sample that has minimum imbalance with respect to the treatment sample, and then use this control subset for estimating the treatment effect. While this optimization problem is NP-hard in general, certain special cases can be solved efficiently. Specifically, the variant of this optimization problem with one covariate is easy to solve, the variant with three or more covariates is NP-hard, and the variant with two covariates is solvable in polynomial time. We present several network flow formulations for the problem of minimizing imbalance on two nominal covariates. First, we present a minimum cost network flow formulation for solving the problem with the constraint that the control subset must have the same size as the treatment sample. We then derive an improved maximum flow formulation. For alternate size restrictions on the control subset, we use a proportional imbalance objective which leads to non-integral supplies and demands in the preceding network flow formulations. We then derive an alternate minimum cost network flow formulation that ensures integrality and solves the proportional imbalance problem in polynomial time.

After a disaster, often roads are damaged and blocked, hindering accessibility for relief efforts. It is essential to dispatch work teams to restore the blocked roads by clearance or repair operations. With the goal of enabling access between critical locations in the disaster area in shortest time, we propose algorithms that determine the schedule and routes of multiple work teams. We minimize the total latency of reaching the critical locations, where the latency of a location is defined as the time it takes from the start of the operation until its first visit by one of the work teams. Coordination among the teams is needed since some blocked edges might be opened by a certain team and utilized by other teams later on. First, we develop an exact mathematical model that handles the coordination requirement. After observing the intractability of this formulation, we introduce two heuristic methods and a lower bounding procedure. In the first method, we develop a mathematical model based on a novel multi-level network representation that yields solutions with disjoint paths. Given that it does not coordinate the teams, we present a matheuristic based on a cluster-first-route-second approach embedded into a local search algorithm together with an additional coordination step to obtain alternative solutions with higher quality and in a shorter time. We test our heuristics on data sets coming from a real network from the literature (180 instances) and randomly generated ones (640 instances) and observe the superiority of the solutions obtained by incorporation of coordination., NA

Recent developments on identifying the community structures in real-world networks have established that the community structure may be either disjoint community set (DCS) or overlapping community set (OCS), showing high resemblance with each other. Still, given a network, researchers mostly followed distinct approaches to achieve optimal solutions, either for DCS or for OCS. Moreover, prior knowledge of community structure is needed to select the appropriate class of algorithms, since one cannot produce the optimal solution for the other. In this article, a comprehensive two-phase approach based on genetic algorithm (GA) is proposed that can be applied to any small-world network to generate the DCS and the OCS very fast without any prior knowledge of the community structure. In the first phase, an upper bound on the mean path length of a community is applied, relative to the equivalent Erdős-Renyi (E-R) random graph that expedites the convergence significantly. In the second phase, the search space is reduced considerably, by selecting a smaller subset of boundary nodes of the DCS generated in the first phase, to be manipulated probabilistically. To the best of our knowledge, we are the first to consider the mean path length of the community as a key parameter for finding the good quality communities at the earliest. Experimental study on six synthetic networks and five real-world networks shows that the proposed approach not only outperforms the state-of-the-art algorithms in terms of quality and scalability, but its parallel implementation also improves the speedup significantly.

There are numerous coverage algorithms which efficiently monitor targets in sensor networks by dividing the sensor network into cover sets where each cover monitors all the targets. Creating maximum number of cover sets is a NP Complete problem and therefore problems providing subprime solutions have been proposed. In this paper we propose a novel and energy efficient target coverage algorithm that produces disjoint as well as non-disjoint cover sets. Our proposed solution along with generating cover sets for monitoring targets also gives the energy optimized minimum path from sink to the sensor node and from cover set to the sink. Our algorithm keeps a track of the number of targets a sensor is monitoring along with the energy remaining to find a path which is energy optimized to increase the lifetime of the sensor network. Through simulations, we have shown that our proposed algorithm outperforms similar algorithms found in literature. The increased network lifetime provided by energy optimized path and energy efficient cover sets makes our algorithm desirable for a wider range of applications.

We characterise directed graphs consisting of disjoint cycles via their talented monoids. We show that a graph $E$ consists of disjoint cycles precisely when its talented monoid $T_E$ has a certain Jordan-H\"older composition series. These are graphs whose associated Leavitt path algebras have finite Gelfand-Kirillov dimension (GKdim). We show that this dimension can be determined as the length of certain ideal series of the talented monoid. Since $T_E$ is the positive cone of the graded Grothendieck group $K_0^{gr}(L_K (E))$, we conclude that for graphs $E$ and $F$, if $K_0^{gr}(L_K (E))\cong K_0^{gr}(L_K (F))$ then $GKdim L_K(E) = GKdim L_K(F)$, thus providing more evidence for the Graded Classification Conjecture for Leavitt path algebras., Comment: 13 pages. Comments welcome!

Reachability queries ask whether a vertex can reach another vertex on large directed graphs. It is one of the most fundamental graph operators and has attracted researchers in both academics and industry to study it. The main technical challenge is to support fast reachability queries by efficient managing the three main costs: the index construction time, the index size and the query processing time on large/small and sparse/dense graphs. As real world graphs grow bigger in size, these problems remain open challenges that demand high performance solutions. In this paper, we propose a Multi-Dimensional Graph Labeling approach (called MGTag) to supporting fast reachability queries. MGTag is novel in three aspects. First, it recursively partitions a graph into multiple subgraphs with disjoint vertex sets, called non-shared graphs, and several inter-partition edges, called cross-edges. Second, we build a four-dimensional label - one dimension of layer, one dimension of non-shared graph and two dimensions of interval for each vertex in non-shared graphs. Finally, with the four-dimensional labeling scheme, we design algorithms to answer reachability queries efficiently. The extensive experiments on 28 large/small and dense/sparse graphs show that building the high dimensional index is quickly and the index size is also competitive compared with most of the state-of-the-art approaches. The results also show that our approach is more scalable and efficient than the state-of-the-art approaches in answering reachability queries on large/small and sparse/dense graphs.

Joint pilot and data power control (JPDPC) is known to have a large impact on both the overall spectral/energy efficiency and fairness of cell-based systems. However, the impact of JPDPC on the inherent spectral/energy efficiency and fairness trade-off in cell-free (CF) systems is much less understood. In this paper, considering pilot contamination, user-centric clustering and multi-antenna access points, we formulate novel JPDPC problems in CF systems as distinct optimization tasks, whose objectives are maximizing the minimum spectral efficiency (SE), maximizing the total SE and maximizing the product of the individual signal-to-interference-plus-noise ratios. Since these problems are non-convex, we solve them by combining successive convex approximation and geometric programming. To the best of our knowledge, this is the first paper analyzing and optimizing JPDPC in user-centric CF systems. Our results indicate that JPDPC allows users to save more energy than the disjoint optimization of pilot and data powers when maximizing the minimum SE, while showing that JPDPC plays a crucial role in balancing between SE and fairness also in CF systems.

Occupancy grids encode for hot spots on a map that is represented by a two dimensional grid of disjoint cells. The problem is to recursively update the probability that each cell in the grid is occupied, based on a sequence of sensor measurements from a moving platform. In this paper, we provide a new Bayesian framework for generating these probabilities that does not assume statistical independence between the occupancy state of grid cells. This approach is made analytically tractable through the use of binary asymmetric channel models that capture the errors associated with observing the occupancy state of a grid cell. Binary-valued measurement vectors are the thresholded output of a sensor in a radar, sonar, or other sensory system. We compare the performance of the proposed framework to that of the classical formulation for occupancy grids. The results show that the proposed framework identifies occupancy grids with lower false alarm and miss detection rates, and requires fewer observations of the surrounding area, to generate an accurate estimate of occupancy probabilities when compared to conventional formulations.

To aggregate useful information among diversified sources, a hotspot research topic called truth discovery has emerged in recent years. Existing truth discovery methods attempt to infer the true attribute values for the entities by identifying and trusting reliable data sources. However, all these methods neglect the relations among different entities, which play important roles in truth discovery task. When reliable data sources cannot provide sufficient information of entities, the true attribute values of these entities can still be inferred by propagating trustworthy information from related entities. Motivated by this, in this paper, we introduce the constrained truth discovery problem. We incorporate denial constraints, a universally quantified first-order logic formalism, into the process of truth discovery. We formulate it as a constrained optimization problem and analyze its hardness. To address the problem, we propose algorithms to partition the entities into disjoint groups, and generate arithmetic constraints for each disjoint group separately. Then, the true attribute values of the entities in each disjoint group are derived by minimizing the objective function under the corresponding arithmetic constraints. Experimental results on both real-world and synthetic datasets demonstrate that the proposed approach achieves good performance even with very few constraints and reliable sources.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms., Comment: 14 pages, 7 figures

Let G = ( V , E ) be a connected graph. H denotes a family of pairwise disjoint graphs { H v } v ∈ V . The Zykov sum of G and H , denoted by G [ H ] , is the graph obtained from G by replacing every vertex v of G with graph H v and all vertices of H u , H v are adjacent if u v ∈ E . In this paper, we first give a decomposition formula for the independence polynomial I G [ H ] ; x . Then, we derive a formula expressing the Fibonacci number of G [ H ] in terms of the independence polynomial of graph G and the Fibonacci number of H v . Finally, as applications, we compute the independence polynomials and the Fibonacci numbers of several interesting graphs, such as the windmill graphs, the path network and the ring network.

Problem definition: We consider an intermediary’s problem of dynamically matching demand and supply of heterogeneous types in a periodic-review fashion. Specifically, there are two disjoint sets of demand and supply types, and a reward for each possible matching of a demand type and a supply type. In each period, demand and supply of various types arrive in random quantities. The platform decides on the optimal matching policy to maximize the expected total discounted rewards, given that unmatched demand and supply may incur waiting or holding costs, and will be fully or partially carried over to the next period. Academic/practical relevance: The problem is crucial to many intermediaries who manage matchings centrally in a sharing economy. Methodology: We formulate the problem as a dynamic program. We explore the structural properties of the optimal policy and propose heuristic policies. Results: We provide sufficient conditions on matching rewards such that the optimal matching policy follows a priority hierarchy among possible matching pairs. We show that those conditions are satisfied by vertically and unidirectionally horizontally differentiated types, for which quality and distance determine priority, respectively. Managerial implications: The priority property simplifies the matching decision within a period, and the trade-off reduces to a choice between matching in the current period and that in the future. Then the optimal matching policy has a match-down-to structure when considering a specific pair of demand and supply types in the priority hierarchy.

In this paper, we define the operational and denotational semantics of a special class of parallel quantum programs, namely disjoint parallel quantum programs. Based on them, a proof system for reasoning about disjoint parallel quantum programs is developed, which is (relatively) complete even when entanglement between different processes appears in the preconditions and postconditions.

Funding: The first author is supported by an Engineering and Physical Sciences Research Council grant (EP/P015638/1). The second author is supported by a Royal Society University Research Fellowship (URF\R\180015). Let H ≤ Sn be an intransitive group with orbits Ω1, Ω2, ... , Ωk. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω1 x H|Ω2 x ... x H|Ωk. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Πc∈P H|c and we demonstrate its usefulness in some applications. Postprint

The 3-D point cloud segmentation has played an important role in spatial structure analysis. Nowadays, segmentation methods either use a primitive-based strategy to fit points in predefined geometric shapes or group points based on their attributes (e.g., spatial distance). However, the required segmentation results, e.g., primitive level or object level, depend on the application. Therefore, this letter develops a semiautomatic method to extract contours for the users' desired segmentation. First, we initialize a 3-D closed curve for the target. Second, we calculate the internal and external force based on the proposed vector flow to deform the curve. The deformation equation is solved based on the Euler equation and calculated iteratively. Finally, the curve is converged as object contours. After one removes contours, those disjoint points are grouped as the users' desired instances. Experiments are conducted on various point clouds to demonstrate the effectiveness in terms of accuracy and consistency. Our quantitative evaluation outperformed selected primitive- and object-based methods, which presents a new viewpoint to the point cloud processing.

Let $E$ be a rearrangement invariant (r.i.) function space on $[0,1]$, and let $Z_E$ consist of all measurable functions $f$ on $(0,\infty)$ such that $f^*\chi_{[0,1]}\in E$ and $f^*\chi_{[1,\infty)}\in L^2$. We reveal close connections between properties of the generalized Rosenthal's space, corresponding to the space $Z_E$, and the behaviour of independent symmetrically distributed random variables in $E$. The results obtained are applied to consider the problem of the existence of isomorphisms between r.i.\ spaces on $[0,1]$ and $(0,\infty)$. Exploiting particular properties of disjoint sequences, we identify a rather wide new class of r.i.\ spaces on $[0,1]$ ``close'' to $L^\infty$, which fail to be isomorphic to r.i.\ spaces on $(0,\infty)$. In particular, this property is shared by the Lorentz spaces $\Lambda_2(\log^{-\alpha}(e/u))$, with $0, Comment: submitted

Publisher Summary This chapter discusses the process of object classification with the very useful maximum-likelihood method. One straightforward and quite powerful approach is the use of the Bayes maximum-likelihood classifier. It generates second-order surfaces that partition the color space into disjoint regions, one for each object type (i.e., for each color of pixel). Assuming Gaussian distributions for the clusters of points in color space, the Bayes classifier maximizes the probability that each pixel will be assigned correctly. The first step is to train the classifier to recognize the three types of pixels. This requires a training set containing pixels that are known to fall in the background, inside normal cells, and inside abnormal cells. It is the statistics of these training set pixels that constitute the knowledge the classifier has about the problem. Estimating these statistics is the process of classifier training.

For k ≥ 2 , spanning trees T 1 , T 2 , … , T k in a graph G are called to be completely independent if for any two distinct vertices x and y , the paths connecting them in T 1 , T 2 , … , T k are pairwise openly disjoint. We call such spanning trees T 1 , T 2 , … , T k the completely independent spanning trees (CIST for short). Recently, Hong and Zhang (2020) found that a sufficient condition for Hamiltonian graphs also suffices the existence of two CISTs. That is, if G is a graph with n vertices, | N ( x ) ∪ N ( y ) | ≥ n 2 and | N ( x ) ∩ N ( y ) | ≥ 3 for every two non-adjacent vertices x , y of G and n ≥ 5 , then G has two CISTs. More recently, Qin et al. (2020) proposed that the restriction on the number of vertices in the statement should be n ≥ 8 , and then pointed out that the Claim 1 in Hong’s paper is not always true for general case, which was corrected by presenting an amendment. However, there still exists a flaw in the corresponding revised proof (see details from the second part of our paper). Accordingly, we give a new amendment to correct the proof.

In the area of change detection, there were a rare number of optimization methods. Most of the optimization methods that are used by change detection are morphological transformation or median filtering, which cannot best optimize change detection algorithm. In this paper, a general post-processing algorithm for change detection is proposed. We believe that some problems cannot be avoided in the area of change detection such as 1) region of moving object generated by change detection is slightly larger than the ground-truth and 2) there are always some disjoint and small regions that are independent from the moving objects. To address the problem, our method can optimize the change detection algorithm bases on the idea of edge detection, which can remove the wrong edge or pixel. In the experiments, more than 20 change detection algorithms that include the best algorithm in ChangeDetection.net are selected. Most of these change detection algorithms are optimized by the proposed method on PWC, Precision, and FMeasure, where, our optimized algorithm named FgSegNet_v2 is better than all other algorithms in the CDnet. The best-optimized margin of PWC is 0.64, and the fast speed is 548FPS on CPU. Our approach can better resolve the afore-mentioned problems that cannot be avoided and is general and fast. The experiments can be reproduced with C++ on Github https://github.com/walty19950301/CDA-contour-optimizer.

One of most central issues in various interconnection networks of parallel and distributed systems is to find edge-disjoint paths concerned with an information transmission through links. It is universally acknowledged that an interconnection network can be modeled as an undirected simple graph G = ( V , E ) with processors and physical links between the processors represented as vertices and edges of the G, respectively. The studies on the edge-disjoint paths are closely related to the edge-connectivity. By the well-known Menger theorem, the maximum number of edge disjoint paths connecting any two disjoint connected subgraphs with g vertices in G can also define by the minimum modified edge-cut, called the g-extra edge-connectivity of G λ g ( G ) . It is the cardinality of the minimum set of edges in G, if such a set exists, whose deletion disconnects G and leaves every remaining component with at least g vertices. The k-ary n-cube network is known as one of the most attractive interconnection networks for parallel and distributed systems. This article intends to show that for 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ ≤ g ≤ 3 ⌈ n 2 ⌉ + r , the g-extra edge-connectivity of ternary n-cube (also called 3-ary n-cube) ( n ≥ 3 ) exists a concentration behavior, and prove that these corresponding g-extra edge-connectivities of ternary n-cubes are the constants 2 ( ⌊ n 2 ⌋ − r ) 3 ⌈ n 2 ⌉ + r , where r = 0 , 1 , 2 , ⋯ , ⌊ n 2 ⌋ − 1 , and e = 1 if n is odd and e = 0 if n is even. The above upper and lower bounds of g are sharp. As the integer g varies within the range between 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ and 3 ⌈ n 2 ⌉ + r , a necessary and sufficient condition of λ g -optimality is found. Our results improve the several previous results.

We develop the Gompf fiber connected sum operation for symplectic orbifolds. We use it to construct a symplectic 4-orbifold with b 1 = 0 {b_{1}=0} and containing symplectic surfaces of genus 1 and 2 that are disjoint and span the rational homology. This is used in turn to construct a K-contact Smale–Barden manifold with specified 2-homology that satisfies the known topological constraints with sharper estimates than the examples constructed previously. The manifold can be chosen spin or non-spin.

The bubble-sort graph network B n is recognized as an attractive interconnection network topology for building multiprocessor computer systems. In this paper, the subnetwork reliability of B n is analyzed in the presence of node failures. An upper bound and a lower bound on the B n − 1 subnetwork reliability of B n are established under the probability fault model, and the theoretical results are proved to be in accordance with and near to the simulation results. Moreover, under the node fault model, the mean time to failure to maintain the fault-free status of different number of disjoint B n − 1 subnetworks in B n is evaluated by using the fixed partitioning and the flexible partitioning, respectively, and it is shown that B n has better robustness under the flexible partitioning pattern when disjoint B n − 1 subnetworks need to be used.

V. V. Grushin and V. P. Palamodov proved in 1962 that it is impossible to place in [Formula: see text] uncountably many pairwise disjoint polyhedra each homeomorphic to the Moebius band. We generalize this result in two directions. First, we give a generalization of this result to tame subsets in [Formula: see text], [Formula: see text]. Second, we show that in case of [Formula: see text] the theorem holds for arbitrarily topologically embedded (not necessarily tame) Moebius bands.

During peak-hour busy airports have the challenge of turning aircraft around as quickly as possible, which includes sequencing their landings and take-offs with maximum efficiency, without sacrificing safety. This problem, termed aircraft sequencing problem (ASP) has traditionally been hard to solve optimally in real-time, even for flights over a one-hour planning window. In this article, we present a novel data-splitting algorithm to solve the ASP on a single runway with the objective to minimize the total delay in the system both under segregated and mixed mode of operation. The problem is formulated as a 0–1 mixed integer program, taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting. Following divide-and-conquer paradigm, the algorithm divides the given set of flights into several disjoint subsets, each of which is optimized using 0–1 MIP while ensuring the optimality of the entire set. One hour peak-traffic instances of this problem, which is NP-hard in general, are computationally difficult to solve with direct application of the commercial solver, as well as existing state-of-the-art dynamic programming method. Using our data-splitting algorithm, various randomly generated instances of the problem can be solved optimally in near real-time, with time savings of over 90%. Civil Aviation Authority of Singapore (CAAS) Nanyang Technological University This research has been partially supported under ATMRI (NTU-CAAS) Grant No. M4061216.

This paper aims to define and study unbounded fuzzy norm convergence in fuzzy Banach lattice, closely related to unbounded fuzzy order convergence. Some other theoretical concepts like fuzzy quasi-interior point and disjoint sequences are studied in relation to unbounded fuzzy norm convergence. Moreover, we defined a topology that is compatible with unbounded fuzzy norm convergence.

For fixed $r\geq 3$ and $n$ divisible by $r$, let ${\mathcal H}={\mathcal H}^r_{n,M}$ be the random $M$-edge $r$-graph on $V=\{1,\ldots ,n\}$; that is, ${\mathcal H}$ is chosen uniformly from the $M$-subsets of ${\mathcal K}:={V \choose r}$ ($:= \{\mbox{$r$-subsets of $V$}\}$). Shamir's Problem (circa 1980) asks, roughly, for what $M=M(n)$ is ${\mathcal H}$ likely to contain a perfect matching (that is, $n/r$ disjoint $r$-sets)? In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\log n$. More recently the author proved the asymptotically correct version of that result: for fixed $C> 1/r$ and $M> Cn\log n$, $P({\mathcal H} ~\mbox{contains a perfect matching})\rightarrow 1 \,\,\, \mbox{as $n\rightarrow\infty$}.$ The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: $\mbox{Theorem.}$ If $A_1, \ldots ~$ is a uniform permutation of ${\mathcal K}$, ${\mathcal H}_t=\{A_1\dots A_t\}$, and \[ T=\min\{t:A_1\cup \cdots\cup A_t=V\}, \] then $P({\mathcal H}_T ~\mbox{contains a perfect matching})\rightarrow 1 \,\,\, \mbox{as $n\rightarrow\infty$}$.

Zero-Shot Learning (ZSL) has gained growing attention over the past few years mostly because it provides a significant scalability to recognition models for classifying instances from new unobserved classes. This scalability is achieved by providing semantic information about new classes, which could be obtained remarkably easier with lower cost, compared to collecting a new training set. Because seen and unseen classes are completely disjoint, ZSL methods often suffer from domain shift problem that occurs in transferring the knowledge of seen classes to unseen ones. Moreover, hubness problem that usually arises in high-dimensional space is another challenge in most ZSL methods due to applying nearest neighbor search for classification. To address these issues, a kernelized distance function is learned in order to discriminate the classes with a customized large-margin loss function. Furthermore, a simple theoretical-based prototype learning approach is provided by defining a non-linear mapping function to learn the visual prototype of each class from associated semantic information. For classification task, the learned distance function is utilized to measure the distance between instances and class-related prototypes. The evaluation on five benchmarks demonstrates the superiority of the proposed method over the state-of-the-art approaches in both zero-shot and generalized zero-shot learning problems.

Efficient tag identification is critically important for the application of radio frequency identification (RFID). The recently proposed orthogonal coset identification (OCSID) achieves orthogonal tag ID scanning without spectrum spreading so that the tag IDs can be recovered from collision. In the OCSID, the IDs are generated from binary vector set $\{-1, +1\}^{B}$ , which is only available for binary modulation. In this letter, we show that $B$ dimensional $M$ order vector set $\left\{{1, e^{\mathrm {i}\frac {2\pi }{M}}, {\dots }, e^{\mathrm {i}\frac {2\pi (M-1)}{M}}}\right\}^{B}$ can be decomposed to $\frac {M^{B}}{B}$ disjoint orthogonal subsets, where $M$ is the modulation order, $B$ is a positive integer power of 2. Based on this, we generalize the OCSID from binary to arbitrary order and propose $M$ -ary phase shift keying (MPSK) OCSID. We show a possible way to adopt the MPSK OCSID into EPC global C1 Gen2 standard, and with the consideration of the synchronization error, we also present a hybrid of the MPSK OCSID and the Aloha. Numerical results show that the MPSK OCSID based protocol can considerably improve the efficiency, even for the non-perfect synchronization cases.

Determining the correct number of clusters is essential for efficient clustering and cluster validity indices are widely used for the same. Generally, the effectiveness of a cluster validity index relies on two factors: first, separation, defined by the distance between a pair of cluster centroids or a pair of data points belonging to different clusters and second, compactness, which is determined in terms of the distance between a data point and a centroid or between a pair of data points belonging to the same cluster. However, the existing cluster validity indices for centroid-based clustering are unreliable when the clusters are too close, but corresponding centroids are distant. To mitigate this, a new cluster validity index, Saraswat-and-Mittal index, has been proposed in this article for hyperellipsoid or hyperspherical shape close clusters with distant centroids, generated by fuzzy c-means. The proposed index computes compactness in terms of the distance between data points and corresponding centroids, whereas the distance between data points of disjoint clusters defines separation. These parameters benefit the proposed index in the analysis of close clusters with distinct centroids efficiently. The performance of the proposed index is validated against ten state-of-the-art cluster validity indices on artificial, UCI, and image datasets, clustered by the fuzzy c-means.

Graph alignment, also known as network alignment has many applications in data mining tasks. It aims to find the node correspondence across disjoint graphs. Recently, various methods like representation learning methods, spectral methods have been proposed to solve the graph alignment problem, but they either only consider the local structure information but ignore the neighborhood similarity, or their alignment process is easy to be disturbed by nodes with similar structure or attribute. In this paper, we consider both center and neighborhood similarities, aiming to reduce the inconsistency between them and enlarge the difference among node representations. We further propose model DGAN(Deep Graph Alignment Network) containing the DNN module and GCN module to learn more unique node representations under the guidance of the attribute-supervised module. Moreover, we theoretically prove that most spectral methods can be unified into a linear GCN model. By extensive experiments on public benchmarks, we show that our model achieves a good balance between alignment accuracy and speed over multiple datasets compared with existing methods.

The knapsack problem with conflicting items arises in several real-world applications. We propose a family of strong cutting planes and prove that a subfamily of these cuts can be facet-defining. Computational experiments show that the proposed cuts are very effective in reducing integrality gaps, providing dual bounds up to 78% tighter than formulations strengthened with traditional combinatorial cuts. We also show that it is possible to adapt a recently proposed lifting procedure to further strengthen the proposed cuts.

The cut-and-project method may be applied to graphs and complexes, although there are technical difficulties, most notably “collisions,” i.e. when the images (under the projection) of two disjoint edges or cells intersect. Given a particular periodic structure, a particular projection space, an appropriate “window” in the orthogonal complement of that space, the induced substructure within the cartesian product of the window and the projection space is projected to the projection space to produce a “model structure.” We may use an index space of vectors from the orthogonal complement to move the window around and obtain a “model system” of model structures. We adapt the notion of “general position” to higher dimensions: the projection space is in “doubly general position” with respect to a graph or complex when the projection of that structure maps vertices of that structure injectively into the projection space and the edges or polytopes of that structure injectively so that their dimension is not reduced and disjoint edges and polytopes remain disjoint. We find that if the initial structure was a periodic graph, if the projection space and its complement are in general position with respect to the vertices and edges, and the window is also in general position, then the model system has uncountably many isomorphism classes - with distinct coordination sequences.

Aharoni and Howard, and, independently, Huang, Loh, and Sudakov proposed the following rainbow version of Erd\H{o}s matching conjecture: For positive integers $n,k,m$ with $n\ge km$, if each of the families $F_1,\ldots, F_m\subseteq {[n]\choose k}$ has size more than $\max\{\binom{n}{k} - \binom{n-m+1}{k}, \binom{km-1}{k}\}$, then there exist pairwise disjoint subsets $e_1,\dots, e_m$ such that $e_i\in F_i$ for all $i\in [m]$. We prove that there exists an absolute constant $n_0$ such that this rainbow version holds for $k=3$ and $n\geq n_0$. We convert this rainbow matching problem to a matching problem on a special hypergraph $H$. We then combine several existing techniques on matchings in uniform hypergraphs: find an absorbing matching $M$ in $H$; use a randomization process of Alon et al. to find an almost regular subgraph of $H-V(M)$; and find an almost perfect matching in $H-V(M)$. To complete the process, we also need to prove a new result on matchings in 3-uniform hypergraphs, which can be viewed as a stability version of a result of {\L}uczak and Mieczkowska and might be of independent interest., Comment: added two references [2,7], accepted for publication in SCIENCE CHINA Mathematics

In set theory without the Axiom of Choice ( $\mathsf {AC}$ ), we investigate the open problem of the deductive strength of statements which concern the existence of almost disjoint and maximal almost disjoint (MAD) families of infinite-dimensional subspaces of a given infinite-dimensional vector space, as well as the extension of almost disjoint families in infinite-dimensional vector spaces to MAD families.

It is a fundamental problem to determine the equivalence of indexed differential polynomials in both computer algebra and differential geometry. However, in the literature, there are no general computational theories for this problem. The main reasons are that the ideal generated by the basic syzygies cannot be finitely generated, and it involves eliminations of dummy indices and functions. This paper solves the problem by extending Grobner basis theory. The authors first present a division of the set of elementary indexed differential monomials $$E_{\partial\kern-0.35em\raise0.22ex\hbox{/}}$$ into disjoint subsets, by defining an equivalence relation on $$E_{\partial\kern-0.35em\raise0.22ex\hbox{/}}$$ based on Leibniz expansions of monomials. The equivalence relation on $$E_{\partial\kern-0.35em\raise0.22ex\hbox{/}}$$ also induces a division of a Grobner basis of basic syzygies into disjoint subsets. Furthermore, the authors prove that the dummy index numbers of the sim-monomials of the elements in each equivalence class of $$E_{\partial\kern-0.35em\raise0.22ex\hbox{/}}$$ have upper bounds, and use the upper bounds to construct fundamental restricted rings. Finally, the canonical form of an indexed differential polynomial proves to be the normal form with respect to a subset of the Grobner basis in the fundamental restricted ring.

We investigate the emergence of spanning structures in sparse pseudo-random $k$-uniform hypergraphs, using the following comparatively weak notion of pseudo-randomness. A $k$-uniform hypergraph $H$ on $n$ vertices is called $(p,\alpha,\epsilon)$-pseudo-random if for all (not necessarily disjoint) vertex subsets $A_1,\dots, A_k{\subseteq} V(H)$ with $|A_1|\cdots |A_k|{\geq}\alpha n^{k}$ we have $$e(A_1,\dots, A_k)=(1\pm\epsilon)p |A_1|\cdots |A_k|.$$ For any linear $k$-uniform $F$ we provide a bound on $\alpha=\alpha(n)$ in terms of $p=p(n)$ and $F$, such that (under natural divisibility assumptions on $n$) any $k$-uniform $\big(p,\alpha, o(1)\big)$-pseudo-random $n$-vertex hypergraph $H$ with a mild minimum vertex degree condition contains an $F$-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence, $\big(p,\alpha, o(1)\big)$-pseudo-random $k$-graphs as above contain: $(i)$ a perfect matching if $\alpha=o(p^{k})$ and $(ii)$ a loose Hamilton cycle if $\alpha=o(p^{k-1})$. This extends the works of Lenz--Mubayi, and Lenz--Mubayi--Mycroft who studied the analogous problems in the dense setting.

Anchor-based techniques reduce the computational complexity of spectral clustering algorithms. Although empirical tests have shown promising results, there is currently a lack of theoretical support for the anchoring approach. We define a specific anchor-based algorithm and show that it is amenable to rigorous analysis, as well as being effective in practice. We establish the theoretical consistency of the method in an asymptotic setting where data is sampled from an underlying continuous probability distribution. In particular, we provide sharp asymptotic conditions for the number of nearest neighbors in the algorithm, which ensure that the anchor-based method can recover with high probability disjoint clusters that are mutually separated by a positive distance. We illustrate the performance of the algorithm on synthetic data and explain how the theoretical convergence analysis can be used to inform the practical choice of parameter scalings. We also test the accuracy and efficiency of the algorithm on two large scale real data sets. We find that the algorithm offers clear advantages over standard spectral clustering. We also find that it is competitive with the state-of-the-art LSC method of Chen and Cai (Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011), while having the added benefit of a consistency guarantee.

Semi-bent functions play an important role in symmetric ciphers and sequence designs. So far, there are few studies related to the construction of vectorial semi-bent functions even though lots of work has been done on single-output semi-bent functions. In this paper, three classes of balanced vectorial semi-bent functions are presented with varying cryptographic properties. The classes denoted $${{\mathcal {D}}}{{\mathcal {C}}}$$ and $${{\mathcal {D}}}{{\mathcal {S}}}$$ are constructed using disjoint codes and disjoint spectra functions, respectively. The former class has a useful provable property that its component functions do not admit linear structures. It is shown that the number of output bits of the constructed n-variable $${{\mathcal {D}}}{{\mathcal {C}}}$$ and $${{\mathcal {D}}}{{\mathcal {S}}}$$ vectorial functions can respectively reach $$(n+1)/2$$ and n/3. In addition, a construction method of semi-bent functions from $${\mathbb {F}}_2^{3n} \rightarrow {\mathbb {F}}_2^n$$ by using almost bent (AB) functions on $${\mathbb {F}}_2^n$$ is given.

A simple $$(2,3,v)$$ trade is a pair $$(T_0,T_1)$$ of disjoint sets of $$3$$ -subsets (blocks) of a $$v$$ -set such that any two elements meet the same number of times in the blocks of $$T_0$$ and the blocks of $$T_1$$ . The size of $$T_0$$ equals the size of $$T_1$$ and is called the volume of the trade. In this paper, for $$v=4n+2$$ , we introduce a new partitioning of the set of all 3-subsets of a v-set into the trades of volume $$4$$ , $$6$$ , and $$8$$ .

We investigate the time evolution of odd entanglement entropy (OEE) and logarithmic negativity (LN) for the thermofield double (TFD) states in free scalar quantum field theories using the covariance matrix approach. To have mixed states, we choose non-complementary subsystems, either adjacent or disjoint intervals on each side of the TFD. We find that the time evolution pattern of OEE is a linear growth followed by saturation. On a circular lattice, for longer times the finite size effect demonstrates itself as oscillatory behavior. In the limit of vanishing mass, for a subsystem containing a single degree of freedom on each side of the TFD, we analytically find the effect of zero-mode on the time evolution of OEE which leads to logarithmic growth in the intermediate times. Moreover, for adjacent intervals we find that the LN is zero for times $t < \beta/2$ (half of the inverse temperature) and after that, it begins to grow linearly. For disjoint intervals at fixed temperature, the vanishing of LN is observed for times $t, Comment: 44 pages, 17 figures, Comments about memory effect and some references are added