The node cover problem is the problem of determining the minimum size (or weight in the weighted version) node set C in an undirected graph G, so that every edge of G is incident with at least one node of C. Both the...
详细信息
The node cover problem is the problem of determining the minimum size (or weight in the weighted version) node set C in an undirected graph G, so that every edge of G is incident with at least one node of C. Both the weighted and unweighted versions can be estimated to within a factor of 2. There are several intuitive factor-of-2 estimations for the unweighted problem, but the algorithms for the weighted version are somewhat more complex. Here, a linear time factor-of-2 approximation algorithm is presented, based on a familiar heuristic approach; this algorithm is superficially very different from algorithm BE (Bar-Yehuda and Even, 1981) and contains none of its special operations. Although this algorithm is seemingly different from the BE algorithm, these 2 algorithms are shown to be, in a strong sense, equivalent, and the counter-intuitive operations of algorithm BE can be seen as mechanisms to accelerate the running of the presented algorithm.
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover...
详细信息
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover number of a graph G, denoted by psi(k)(G). It is known that the minimum k-path vertex cover problem (k-PVCP) is NP-hard for all k >= 2. In this paper we consider the weighted version of a k-PVCP (k-WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P-k. This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k-WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k-path vertex cover number of a tree with time complexity O(*** bar V(G)vertical bar) is presented. (C) 2014 Elsevier B.V. All rights reserved.
作者：
Tamura, YumaIto, TakehiroZhou, XiaoTohoku Univ
Grad Sch Informat Sci Sendai Miyagi 9808579 Japan JST
ERATO Kawarabayashi Large Graph Project Global Res Ctr Big Data MathNII Tokyo 1018430 Japan
A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the proble...
详细信息
A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.
Along with the fast development of dual-threshold voltage (dual-V-t) and multi-threshold technology, it is possible to use them to reduce static power in low-voltage high-performance circuits. In this paper, we propos...
详细信息
Along with the fast development of dual-threshold voltage (dual-V-t) and multi-threshold technology, it is possible to use them to reduce static power in low-voltage high-performance circuits. In this paper, we propose a new method to realize CMOS digital circuits that are implemented with dual-V-t technology. We first present a new signal-path-level circuit model which effectively deals with the fact that there can be two threshold voltages assigned to a single gate. In order to assign proper threshold voltage to all the signal-paths in the circuit, our new algorithms introduce the concept of subcircuit extraction and include the hierarchy algorithms which are effective and fast. Experimental results show that our algorithms produce a significant reduction for the ISCAS85 benchmark circuits.
We study the applicability of spiking neural networks and neuromorphic hardware for solving general optimization problems without the use of adaptive training or learning algorithms. We leverage the dynamics of Hopfie...
详细信息
We study the applicability of spiking neural networks and neuromorphic hardware for solving general optimization problems without the use of adaptive training or learning algorithms. We leverage the dynamics of Hopfield networks and spin-glass systems to construct a fully connected spiking neural system to generate synchronous spike responses indicative of the underlying community structure in an undirected, unweighted graph. Mapping this fully connected system to current generation neuromorphic hardware is done by embedding sparse tree graphs to generate only the leading-order spiking dynamics. We demonstrate that for a chosen set of benchmark graphs, the spike responses generated on a current generation neuromorphic processor can improve the stability of graph partitions and non-overlapping communities can be identified even with the loss of higher-order spiking behavior if the graphs are sufficiently dense. For sparse graphs, the loss of higher-order spiking behavior improves the stability of certain graph partitions but does not retrieve the known community memberships.
Token ring topology has been frequently used in the design of distributed loop computer networks and one measure of its performance is the diameter. We propose an algorithm for constructing hamiltonian graphs with n v...
详细信息
Token ring topology has been frequently used in the design of distributed loop computer networks and one measure of its performance is the diameter. We propose an algorithm for constructing hamiltonian graphs with n vertices, maximum degree Delta and diameter O(log n), where n is an arbitrary number. The number of edges is asymptotically bounded by (2 - 1/Delta-t - (Delta-2)(2)/(Delta-1)(3))n. In particular, we construct a family of hamiltonian graphs with diameter at most 2left perpendicularlog(2) nright perpendicular, maximum degree 3 and at most 1 + 11n/8 edges. (C) 2009 Elsevier Ltd. All rights reserved.
Finding k shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen's algorithm and its variants have polynomial worst-case time comp...
详细信息
Finding k shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen's algorithm and its variants have polynomial worst-case time complexity, but their average-case running time is very high. The heuristic algorithm MPS can run significantly faster in practice. However, it requires an excessive amount of memory space. In this paper, we provide a new heuristic algorithm that achieves high space efficiency while maintaining similar average-case running time. We first propose a sidetrack representation of path, with which a path can be stored in O(1) space. We then show how to categorize a candidate path as either partial or complete, and restrict the number of paths added to the queue. In addition, we provide an empirical equation that can very accurately predict the kth shortest path length, provided that a much smaller number of shortest paths have been found. Extensive experiments prove that our algorithm can achieve an O(n) speedup in practice over Yen's algorithm. In comparison with MPS, it runs up to three times faster and uses less space by an order of magnitude.
The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(...
详细信息
The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(1))-time polynomial-space algorithm by Eppstein and the 1.733(n)n(O(1))-time exponential-space algorithm by Gebauer.
A dissociation set in a graph G = (V, E) is a vertex subset D such that the subgraph G[D] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three v...
详细信息
A dissociation set in a graph G = (V, E) is a vertex subset D such that the subgraph G[D] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. A vertex set D is a dissociation set if and only if V \ D is a 3-path vertex cover. There are many applications for dissociation sets and 3-path vertex covers. However, it is NP-hard to compute a dissociation set of maximum size or a 3-path vertex cover of minimum size in graphs. Several exact algorithms have been proposed for these two problems and they can be solved in O*(1.4658(n)) time in n-vertex graphs. In this paper, we reveal some interesting structural properties of the two problems, which allow us to solve them in O*(1.4656(n)) time and polynomial space or O*(1.3659(n)) time and exponential space. (C) 2016 Elsevier B.V. All rights reserved.
A common representational style for drawing graphs is the so-called circular drawings, where vertices are represented as points on a circle, and edges are represented as straight line segments. In such drawings, edges...
详细信息
A common representational style for drawing graphs is the so-called circular drawings, where vertices are represented as points on a circle, and edges are represented as straight line segments. In such drawings, edges may cross;these edge crossings have a negative effect on human readability. Recent empirical research shows that increasing the angles of edge crossings reduces the negative effect of crossings on human readability. This result has motivated a number of recent investigations of right angle crossing graph drawings, where each crossing angle is The main result of this paper is a characterization of graphs that admit a circular right angle crossing drawing. We present a linear-time algorithm for testing and constructing such a drawing of a graph, if it exists. Further, we give an upper bound on the number of edges in a circular right angle crossing drawing, and we note that the optimization problem of constructing circular drawings with large angle crossings can be formulated as a quadratic programming problem. (C) 2016 Elsevier B.V. All rights reserved.
暂无评论