We give the first optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O...
详细信息
We give the first optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G. (C) 2010 Elsevier B.V. All rights reserved.
Let G be a graph, x, y epsilon V(G), and phi : V (G) -> [K] a k-colouring of G such that phi(x) = phi(y). If Delta(G) >= k + root k - 1 then the following question is NP-complete: Does there exist a k-colouring ...
详细信息
Let G be a graph, x, y epsilon V(G), and phi : V (G) -> [K] a k-colouring of G such that phi(x) = phi(y). If Delta(G) >= k + root k - 1 then the following question is NP-complete: Does there exist a k-colouring phi' of such that phi' (x) not equal phi (Y)? Conversely, if Delta(G) <= k +root k - 3 then the problem is polynomial time. (C) 2010 Elsevier B.V. All rights reserved.
The minimum 3-way cut problem in an edge-weighted hypergraph is to find a partition of the vertices into 3 nonempty sets minimizing the total weight of hyperedges that have at least two endpoints in two different sets...
详细信息
The minimum 3-way cut problem in an edge-weighted hypergraph is to find a partition of the vertices into 3 nonempty sets minimizing the total weight of hyperedges that have at least two endpoints in two different sets. In this paper we show that a minimum 3-way cut in hypergraphs can be found by using O(n(3)) hypergraph minimum (s, t) cut computations, where n is the number of vertices in the hypergraph. Our simple algorithm is the first polynomial-time algorithm for finding minimum 3-way cuts in hypergraphs. (C) 2010 Elsevier B.V. All rights reserved.
Recently, a number of variants of the approximate minimum degree algorithm have been proposed that aim to efficiently order symmetric matrices containing some dense rows. We compare the peformance of these variants on...
详细信息
Recently, a number of variants of the approximate minimum degree algorithm have been proposed that aim to efficiently order symmetric matrices containing some dense rows. We compare the peformance of these variants on a range of problems and highlight their potential limitations. This leads us to propose a new variant that offers both speed and robustness. Copyright (C) 2009 John Wiley & Sons, Ltd.
Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G = (V. E) on n vertices, a pair (X. Y), with X, Y s...
详细信息
Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G = (V. E) on n vertices, a pair (X. Y), with X, Y subset of V, X boolean AND Y = mt set, is a non-induced biclique if {x, y} is an element of E for any x is an element of X and y is an element of Y. The NP-complete problem of finding a non-induced (k(1), k(2))-biclique asks to decide whether G contains a non-induced biclique (X. Y) such that vertical bar X vertical bar = k(1) and vertical bar Y vertical bar = k(2). In this paper, we design a polynomial-space O(1.6914(n))-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(1.30052(n)). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(1.30052(n)). (C) 2010 Elsevier B.V. All rights reserved.
In this paper, we present a network flow based approach for dynamic network and channel selection for secondary users in dynamic spectrum access networks. Most approaches in the current literature on dynamic spectrum ...
详细信息
In this paper, we present a network flow based approach for dynamic network and channel selection for secondary users in dynamic spectrum access networks. Most approaches in the current literature on dynamic spectrum access networks do not consider dynamic network and channel selection. We present a network flow framework for network selection. We show that our approach can enable re-assignment of networks to secondary users and also re-assignment of channels to secondary users within the same network. The assignments and re-assignments take into account, the interference caused to primary users, the price each secondary user is willing to pay and the quality of service (QoS) obtained by each secondary user. We obtain a bound for the maximum number of re-assignments. (C) 2009 Elsevier B.V. All rights reserved.
作者：
Lin, LanLin, YixunZhengzhou Univ
Dept Math Zhengzhou 450052 Peoples R China Tongji Univ
Key Lab Embedded Syst & Serv Comp Minist Educ Shanghai 200092 Peoples R China Tongji Univ
Sch Elect & Informat Engn Shanghai 200092 Peoples R China
The two-dimensional bandwidth problem is to embed a graph G into an n x n grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the "distance" has two diff...
详细信息
The two-dimensional bandwidth problem is to embed a graph G into an n x n grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the "distance" has two different meanings: the L-1-norm distance and L-infinity-norm distance. So we have two models of two-dimensional bandwidth problem. This paper investigates the basic properties and relations of these two models. Some lower bounds, upper bounds, and exact results are presented. (C) 2010 Elsevier B.V. All rights reserved.
In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n(3) log(3) log n/log(2) n), which improves all known algorithms for general real...
详细信息
In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n(3) log(3) log n/log(2) n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n(3-(3-omega)/(2d+ 4))), where omega < 2.376;in two dimensions, this is O(n(2.922)). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n(3-(3-omega)/ 4)) = O(n(2.844)) time) for APSP in real-vertex-weighted graphs, as well as an improved result (near O(n((3+omega)/2)) = O(n(2.688)) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.
It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called a pendent pair, and that a minimum cut in a graph can be found by repe...
详细信息
It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called a pendent pair, and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering (MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different type of special pair of vertices, called a flat pair, which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended to the problem of finding extreme subsets in symmetric submodular set functions.
In this paper, we propose a grid-based approach to providing the maximum coverage for a mobile target in a hybrid sensor network. The maximum coverage is achieved by moving mobile sensor nodes in the network based on ...
详细信息
ISBN:
(纸本)9781424455690
In this paper, we propose a grid-based approach to providing the maximum coverage for a mobile target in a hybrid sensor network. The maximum coverage is achieved by moving mobile sensor nodes in the network based on a distributed method. To minimize total movement cost, the proposed approach needs to solve the following problems: the minimum number of mobile sensor nodes used for healing coverage holes and the best matching between the mobile sensor nodes and the coverage holes. In the proposed approach, the above two problems are first transformed into the modified circle covering and minimum cost flow problems, respectively. Finally, we perform simulation experiments to show the effectiveness of proposed approach in providing coverage for a mobile target.
暂无评论