We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm e...
详细信息
We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm edges this algorithm runs inO(n 1/2 m) time.
In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance...
详细信息
In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n(2)) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Omega(n(2)), our algorithm achieves the optimal time complexity.
Current 3D graphics computing systems rely on a massive number of triangles to generate realistic images in embedded systems, on personal computers, and on high-performance workstations. Although the number of triangl...
详细信息
Current 3D graphics computing systems rely on a massive number of triangles to generate realistic images in embedded systems, on personal computers, and on high-performance workstations. Although the number of triangles increases, no specific order for their input sequence exists;thus, many triangles that do not contribute to a final image must still be rasterized and shaded. This study culls invisible triangles using a novel technique that focuses on the depth relationships among triangles before they are shaded and rasterized. The proposed technique can identify overlapped triangles exactly and eliminate these triangles to eliminate unnecessary triangular rasterizing and pixel shading. The simulation result shows this algorithm can eliminate 18-46% of triangles before rasterizing of given benchmarks in a typical 3D graphics hardware pipeline.
We present PuLP (partitioning using label propagation), a parallel and memory efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions on shared-mem...
详细信息
We present PuLP (partitioning using label propagation), a parallel and memory efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions on shared-memory multicore platforms. graph partitioning is an important problem in scientific computing because it impacts the execution time and energy efficiency of computations on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization. A novel feature of our PuLP method is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses up to 7.8x less memory than state-of-the-art partitioners and is 5.0x faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multiobjective scenario.
By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is origin...
详细信息
By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA' 11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.
The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex ...
详细信息
The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars. (C) 2020 Elsevier B.V. All rights reserved.
This paper deals with decomposition of complete graphs on n vertices into circulant graphs with reduced degree r < n - 1. They are denoted as C-n(a(1), a(2), ... , a(m)), where a(1) to a(m) are generators. Mathemat...
详细信息
This paper deals with decomposition of complete graphs on n vertices into circulant graphs with reduced degree r < n - 1. They are denoted as C-n(a(1), a(2), ... , a(m)), where a(1) to a(m) are generators. Mathematical labeling for such bigger (higher order and huge size) and complex (strictly regular with so many triangles) graphs is very difficult. That is why after decomposition, an edge irregular k-labeling for these subgraphs is computed with the help of algorithmic approach. Results of k are computed by implementing this iterative algorithm in computer. Using the values of k, an upper bound for edge irregularity strength is suggested for C-n(a(1), a(2), ... , a(m)) that is vertical bar E vertical bar/2 log(2) vertical bar V vertical bar.
Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness bet...
详细信息
Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called Greedy and SteinerSwap that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem.
We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of O(kn(m + n log n)) and follows the same process as Yen's dev...
详细信息
We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of O(kn(m + n log n)) and follows the same process as Yen's deviation algorithm, but the candidate paths are computed more efficiently using a node classification technique. We first show that a candidate path can be separated by its deviation node as prefix and suffix. Our algorithm then classifies the nodes as red, yellow, and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. We prove that when searching for the suffix of a candidate path, all green nodes can be bypassed, and we only need to apply Dijkstra's algorithm to find an all-yellow-node subpath. Since on average the number of yellow nodes is much smaller than n, the new algorithm has a much lower average-case running time. Experiments on many types of networks demonstrate that the new algorithm performs significantly better than existing exact algorithms that have polynomial worst-case complexity. (C) 2014 Wiley Periodicals, Inc.
The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recent...
详细信息
The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.
暂无评论