Explore the vast range of titles available.

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research has shown that such algorithms show significant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, Lovász and Szegedy [Geom. Funct. Anal. 24 (2014) 269–296] that local algorithms defined specifically as so-called i.i.d. factors may be able to find approximately largest independent sets in random d-regular graphs. In this paper, we refute this conjecture and show that every independent set produced by local algorithms is multiplicative factor 1/2+1/(2√2) smaller than the largest, asymptotically as d → ∞. Our result is based on an important clustering phenomena predicted first in the literature on spin glasses, and recently proved rigorously for a variety of constraint satisfaction problems on random graphs. Such properties suggest that the geometry of the solution space can be quite intricate. The specific clustering property that we prove and apply in this paper shows that typically every two large independent sets in a random graph either have a significant intersection, or have a very small intersection. As a result, large independent sets are clustered according to the proximity to each other. While the clustering property was postulated earlier as an obstruction for the success of local algorithms, our result is the first one where the clustering property is used to formally prove limits on local algorithms.

Given an undirected graph, are there k matchings whose union covers all of its nodes, that is, a matching-k-cover ? When k = 1 , the problem is equivalent to the existence of a perfect matching for which Tutte’s celebrated matching theorem (J. Lon. Math. Soc., 1947) provides a ‘good’ characterization. We prove here, when k is greater than one, a ‘good’ characterization à la Kőnig : for k ≥ 2 , there exist k matchings covering every node if and only if for every stable set S , we have | S | ≤ k · | N ( S ) | . Moreover, somewhat surprisingly, we use only techniques from bipartite matching in the proof, through a simple, polynomial algorithm. A different approach to matching-k-covers has been previously suggested by Wang et al. (Math. Prog., 2014), relying on general matching and using matroid union for matching-matroids, or the Edmonds-Gallai structure theorem. Our approach provides a simpler polynomial algorithm together with an elegant certificate of non-existence when appropriate. Further results, generalizations and interconnections between several problems are then deduced as consequences of the new minimax theorem, with surprisingly simple proofs (again using only the level of difficulty of bipartite matchings). One of the equivalent formulations leads to a solution of weighted minimization for non-negative edge-weights, while the edge-cardinality maximization of matching-2-covers turns out to be already NP-hard. We have arrived at this problem as the line graph special case of a model arising for manufacturing integrated circuits with the technology called ‘Directed Self Assembly’.

The algorithms of tensors’ summing, multiplying and collapsing are observed in that issue from the perspectives of those paralleling possibilities. The graphs of these algorithms are developed and analyzed from the point of the forecasted values of the acceleration and efficiency. It is assumed that the time of execution for all computing operations is same and equal to a unit of time, and data transfer between computer devices is performed instantaneously without any time consuming (it is acceptable, for example, a parallel computing systems with shared memory). In particular, it is shown that for the tensors’ addition the time of the fastest execution of algorithm for an unlimited number of processors is equal to the length of the maximum path in the graph. In other words, the minimum time of the algorithm will be achieved when the number of processors is equal to the number of components of the tensor. A similar analysis was performed for the algorithms of multiplication and convolution of tensors.

The mixture of data in real life exhibits structure or connection property in nature. Typical data include biological data, communication network data, image data, etc. Graphs provide a natural way to represent and analyze these types of data and their relationships. For instance, more recently, graphs have found new applications in solving problems for emerging research fields such as social network analysis, design of robust computer network topologies, frequency allocation in wireless networks, and bioinformatics. Unfortunately, the related algorithms usually suffer from high computational complexity, since some of these problems are NP-hard. Therefore, in recent years, many graph models and optimization algorithms have been proposed to achieve a better balance between efficacy and efficiency. The aim of this Special Issue is to provide an opportunity for researchers and engineers from both academia and the industry to publish their latest and original results on graph models, algorithms, and applications to problems in the real world, with a focus on optimization and computational complexity.

In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.

Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques aim at the identification of vertex subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are: li>What are the communities within an (online) social network? How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer? How must components be organised on a computer chip such that they can communicate efficiently with each other? What are the segments of a digital image? Which functions are certain genes (most likely) responsible for? The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyse various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails. This book is published in cooperation with the Center for Discrete Mathematics and Theoretical Computer Science.

A graph theory based methodology for design of water network partitioning is proposed. Both multiple and single source networks are considered. In the first case the partition refers to the definition of isolated sectors, each of them supplied by its own sources. The shortest paths from each water source to each network node are found and each network node is assigned to be supplied exclusively by the source with the shortest path distance to it. The pipes to be closed are the edge separators of such partition. In the second case the partitioning problem refers to a division of the network in relatively small district metering areas (DMAs) each of them fed by a single pipe. A hierarchical tree for the graph is constructed using a breadth-first search. A recursive approach is applied on this tree to find the design flow rates in each pipe summing the demand of descendant nodes. Based on these flow rates the nodes belonging to each DMA are found. The pipes to be closed are defined as the chords between branches of the hierarchical tree lying below the feeding pipe. The procedure has been tested on a real medium city all-pipe water distribution network model.

This paper presents a new and efficient algorithm, IligraLIGRA , for inverse line graph construction. Given a line graph H , I LIGRA constructs its root graph G with the time complexity being linear in the number of nodes in H . If I LIGRA does not know whether the given graph H is a line graph, it firstly assumes that H is a line graph and starts its root graph construction. During the root graph construction, I LIGRA checks whether the given graph H is a line graph and I LIGRA stops once it finds H is not a line graph. The time complexity of I LIGRA with line graph checking is linear in the number of links in the given graph H . For sparse line graphs of any size and for dense line graphs of small size, numerical results of the running time show that I LIGRA outperforms all currently available algorithms.

Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received attention in the literature as compared to the extensive studies on the guarantees of graph partitioning. For instance, consistency results of spectral graph partitioning under the stochastic block model are well known. In this paper, we present a planted partition model for sparse random nonuniform hypergraphs that generalizes the stochastic block model. We derive an error bound for a spectral hypergraph partitioning algorithm under this model using matrix concentration inequalities. To the best of our knowledge, this is the first consistency result related to partitioning nonuniform hypergraphs.

This paper addresses the problem of segmenting an image into regions. We define a predicate for measuring the evidence for a boundary between two regions using a graph-based representation of the image. We then develop an efficient segmentation algorithm based on this predicate, and show that although this algorithm makes greedy decisions it produces segmentations that satisfy global properties. We apply the algorithm to image segmentation using two different kinds of local neighborhoods in constructing the graph, and illustrate the results with both real and synthetic images. The algorithm runs in time nearly linear in the number of graph edges and is also fast in practice. An important characteristic of the method is its ability to preserve detail in low-variability image regions while ignoring detail in high-variability regions.[PUBLICATION ABSTRACT]