Search

A result of Friedman and Pippenger gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. In this paper, we extend the tree embedding problem of expanding graphs to the degenerate graph embedding problem, and give a sufficient condition for a graph to contain strong 2 -degenerate subgraphs with bounded maximum codegree. [ABSTRACT FROM AUTHOR]

The efficiency of a graph embedding problem when simulating one interconnection network in another interconnection network is characterized by the influential parameter of wirelength. Obtaining the minimum wirelength in an embedding problem determines the quality of that embedding. In this paper, we obtained the convex edge partition of 3-Ary n-Cubes and the minimized wirelength of the embeddings of both 3-Ary n-Cubes and circulant networks. [ABSTRACT FROM AUTHOR]

Graph is an important data representation which appears in a wide diversity of real-world scenarios. Effective graph analytics provides users a deeper understanding of what is behind the data, and thus can benefit a lot of useful applications such as node classification, node recommendation, link prediction, etc. However, most graph analytics methods suffer the high computation and space cost. Graph embedding is an effective yet efficient way to solve the graph analytics problem. It converts the graph data into a low dimensional space in which the graph structural information and graph properties are maximumly preserved. In this survey, we conduct a comprehensive review of the literature in graph embedding. We first introduce the formal definition of graph embedding as well as the related concepts. After that, we propose two taxonomies of graph embedding which correspond to what challenges exist in different graph embedding problem settings and how the existing work addresses these challenges in their solutions. Finally, we summarize the applications that graph embedding enables and suggest four promising future research directions in terms of computation efficiency, problem settings, techniques, and application scenarios. [ABSTRACT FROM AUTHOR]

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(k log k) in the best-known running time, and for a number of such problems we show that the dependence on k in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings s1, ..., st over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings si, 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in times 2O(d log d) · nO(1) and 2O(d log |Σ|) · nO(1). We show that there are no 2o(d log d) · nO(1) or 2o(d log |Σ|) · nO(1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time 2O(w log w) ·nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future. [ABSTRACT FROM AUTHOR]

Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network (the so-called virtual cluster ) to their physical counterparts: a graph embedding problem. However, existing virtual cluster embedding algorithms often ignore a crucial dimension of the problem, namely data locality : the input to a cloud application such as MapReduce is typically stored in a distributed, and sometimes redundant, file system. Since moving data is costly, an embedding algorithm should be data locality aware, and allocate computational resources close to the data; in case of redundant storage, the algorithm should also optimize the replica selection . This paper initiates the algorithmic study of data locality aware virtual cluster embeddings on datacenter topologies. We show that despite the multiple degrees of freedom in terms of embedding, replica selection and assignment, many problems can be solved efficiently. We also highlight the limitations of such optimizations, by presenting several NP-hardness proofs; interestingly, our hardness results also hold in uncapacitated networks of small diameter. [ABSTRACT FROM AUTHOR]

The first part of the paper centers in the study of embeddability between partially commutative groups. In [10], for a finite simplicial graph Γ, the authors introduce an infinite, locally infinite graph Γ e, called the extension graph of Γ . They show that each finite-induced subgraph Δ of Γ e gives rise to an embedding between the partially commutative groups G(Δ) and G(Γ ). Furthermore, it is proved that, in many instances, the converse also holds. Our first result is the decidability of the Extension Graph Embedding Problem: there is an algorithm that given two finite simplicial graphs Δ and Γ decides whether or not Δ is an induced subgraph of Γ e. As a corollary, we obtain the decidability of the Embedding Problem for 2D partially commutative groups. In the second part of the paper, we relate the Embedding Problem between partially commutative groups to the model-theoretic question of classification up to universal equivalence. We use our characterization to transfer algebraic and algorithmic results on embeddability to model-theoretic ones and obtain some rigidity results on the elementary theory of atomic pc groups as well as to deduce the existence of an algorithm to decide if an arbitrary pc group is universally equivalent to a 2D one. [ABSTRACT FROM AUTHOR]

Abstract: The distance preserving graph embedding problem is to embed the vertices of a given weighted graph onto points in d-dimensional Euclidean space for a constant d such that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if the weights are given as a full matrix, then multi-dimensional scaling [Trevor Cox, Michael Cox, Multidimensional Scaling, second ed., Chapman & Hall CRC, 2001] can minimize the sum of squared embedding errors in quadratic time. A serious disadvantage of this approach is its quadratic space requirement. In this paper we develop a linear-space algorithm for this problem for the case when the weight of any edge can be computed in constant time. A key idea is to partition a set of n objects into disjoint subsets (clusters) of size such that the minimum inter cluster distance is maximized among all possible such partitions. Experimental results are included comparing the performance of the newly developed approach to the performance of the well-established least-squares multi-dimensional scaling approach [Trevor Cox, Michael Cox, Multidimensional Scaling, second ed., Chapman & Hall CRC, 2001] using three different applications. Although least-squares multi-dimensional scaling gave slightly more accurate results than our newly developed approach, least-squares multi-dimensional scaling ran out of memory for data sets larger than 15 000 vertices. [Copyright &y& Elsevier]

A well-known problem in protein modeling is the determination of the structure of a protein with a given set of inter-atomic or inter-residue distances obtained from either physical experiments or theoretical estimates. A general form of the problem is known as the distance geometry problem in mathematics, the graph embedding problem in computer science, and the multidimensional scaling problem in statistics. The problem has applications in many other scientific and engineering fields as well such as sensor network localization, image recognition, and protein classification. We describe the formulations and complexities of the problem in its various forms, and introduce a geometric buildup approach to the problem. Central to this approach is the idea that the coordinates of the atoms in a protein can be determined one atom at a time, with the distances from the determined atoms to the undetermined ones. It can determine a structure more efficiently than other conventional approaches, yet without requiring more distance constraints than necessary. [ABSTRACT FROM AUTHOR]

A string p=p0p1⋯pn−1 of non-negative integers is a Euclidean string if the string (p0+1)p1⋯(pn−1−1) is rotationally equivalent (i.e., conjugate) to p. We show that Euclidean strings exist if and only if n and p0+p1+⋯+pn−1 are relatively prime and that, if they exist, they are unique. We show how to construct them using an algorithm with the same structure as the Euclidean algorithm, hence the name. We show that Euclidean strings are Lyndon words and we describe relationships between Euclidean strings and the Stern–Brocot tree, Fibonacci strings, Beatty sequences, and Sturmian sequences. We also describe an application to a graph embedding problem. [Copyright &y& Elsevier]