共查询到20条相似文献,搜索用时 31 毫秒
1.
《国际计算机数学杂志》2012,89(11):2259-2264
An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UBG(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G?S. 相似文献
2.
Abstract. This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n
4
) and O(n
6
) maximum flow computations, respectively, to compute a minimum 3 -way cut and a minimum 4 -way cut of G . In this paper we first show some properties on minimum 3 -way cuts and minimum 4 -way cuts, which indicate a recursive structure of the minimum k -way cut problem when k = 3 and 4 . Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of G , which require O(n
3
) and O(n
4
) maximum flow computations, respectively. 相似文献
3.
In many applications, we need to find a minimum cost partition of a network separating a given pair of nodes. A classical example is the Max-Flow Min-Cut Theorem, where the cost of the partition is defined to be the sum of capacities of arcs connecting the two parts. Other similar concepts such as minimum weighted sparsest cut and flux cut have also been introduced. There is always a cost associated with a cut, and we always seek the min-cost cut separating a given pair of nodes. A natural generalization from the separation of a given pair is to find all minimum cost cuts separating all
pairs of nodes, with arbitrary costs associated with all 2n–1 — 1 cuts. In the present paper, we show thatn — 1 minimum cost cuts are always sufficient to separate all
pairs of nodes.A further generalization is to considerk-way partitions rather than two-way partitions. An interesting relationship exists betweenk-way partitions, the multicommodity flow problem, and the minimum weighted sparsest cut. Namely, if the staturated arcs in a multicommodity flow problem form ak-way partition (k 4), then thek-way partition contains a two-way partition. This two-way partition is the minimum weight sparsest cut.This work is supported in part by the NSF under Grant MIP-8700767 and micro program under Grants 506205 and 506215, Intergraph, and Data General. 相似文献
4.
We study a capacitated network design problem with applications in
local access network design. Given a network, the problem is to route
flow from several sources to a sink and to install
capacity on the edges to support the flow at minimum cost.
Capacity can be purchased only in multiples of a fixed quantity.
All the flow from a source must be routed
in a single path to the sink. This NP-hard problem generalizes the
Steiner tree problem and also more effectively models the applications
traditionally formulated as capacitated tree problems. We present
an approximation algorithm with performance ratio
(ρST + 2) where ρST is the performance ratio of
any approximation algorithm for the minimum Steiner tree problem.
When all sources have unit demand, the ratio
improves to ρST + 1) and, in particular, to 2 when all nodes
in the graph are sources. 相似文献
5.
We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class. 相似文献
6.
The Stackelberg Minimum Spanning Tree Game 总被引:1,自引:0,他引:1
Jean Cardinal Erik D. Demaine Samuel Fiorini Gwena?l Joret Stefan Langerman Ilan Newman Oren Weimann 《Algorithmica》2011,59(2):129-144
We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor??s prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player??s best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min?{k,1+ln?b,1+ln?W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm. 相似文献
7.
This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n 4 ) and O(n 6 ) maximum flow computations, respectively, to compute a minimum 3 -way cut and a minimum 4 -way cut of G . In this paper we first show some properties on minimum 3 -way cuts and minimum 4 -way cuts, which indicate a recursive structure of the minimum k -way cut problem when k = 3 and 4 . Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of G , which require O(n 3 ) and O(n 4 ) maximum flow computations, respectively. 相似文献
8.
We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation
between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory
of Robertson and Seymour, which ultimately proves Wagner’s Conjecture about the structure of minor-closed graph properties.
First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs
and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs
excluding a minor, namely, K
3,k
-minor-free graphs, using new techniques that do not rely on Graph Minor Theory. These two avenues lead to faster fixed-parameter
algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters, which
include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating
set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set, connected R-dominating set, and unweighted TSP tour. Third, we disprove a variation of Wagner’s Conjecture for the case of graph contractions
in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations
of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated
dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence
of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via Graph Minor Theory. 相似文献
9.
10.
We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network
and the maximum degree of any node in the network. A prototypical example is the degree-constrained node-weighted Steiner
tree problem: We are given an undirected graph G(V,E) , with a nonnegative integral function d that specifies an upper bound d(v) on the degree of each vertex v ∈ V in the Steiner tree to be constructed, nonnegative costs on the nodes, and a subset of k nodes called terminals. The goal is to construct a Steiner tree T containing all the terminals such that the degree of any node v in T is at most the specified upper bound d(v) and the total cost of the nodes in T is minimum. Our main result is a bicriteria approximation algorithm whose output is approximate in terms of both the degree
and cost criteria—the degree of any node v ∈ V in the output Steiner tree is O(d(v) log k) and the cost of the tree is O(log k) times that of a minimum-cost Steiner tree that obeys the degree bound d(v) for each node v . Our result extends to the more general problem of constructing one-connected networks such as generalized Steiner forests.
We also consider the special case in which the edge costs obey the triangle inequality and present simple approximation algorithms
with better performance guarantees.
Received December 21, 1998; revised September 24, 1999. 相似文献
11.
Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation. 相似文献
12.
For an edge-weighted connected undirected graph, the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. The problem is NP-hard when k is part of the input and W[1]-hard when k is taken as a parameter. 相似文献
13.
We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number
problem, which arises in the area of computer networks, is the problem of
partitioning a given graph into a maximum number of disjoint dominating
sets. This number is called the domatic number of the graph. We prove that
the problem of determining whether or not the domatic number of a given
graph is exactly one of k given values is complete for
BH2k(NP), the 2kth level of the boolean hierarchy over NP. In
particular, for k = 1, it is DP-complete to determine whether or not
the domatic number of a given graph equals exactly a given integer. Note
that DP = BH2(NP). We obtain similar results for the exact versions
of generalized dominating set problems and of the conveyor flow shop
problem. Our reductions apply Wagner's conditions sufficient to prove
hardness for the levels of the boolean hierarchy over NP. 相似文献
14.
We investigate the probabilistic communication complexity (more exactly, the majority communication complexity), of the graph
accessibility problem (GAP) and its counting versions MOD
k
-GAP,k ≥ 2. Due to arguments concerning matrix variation ranks and certain projection reductions, we prove that, for any partition
of the input variables, GAP and MOD
m
-GAP have majority communication complexity Ω,(n), wheren denotes the number of nodes of the graph under consideration. 相似文献
15.
Among the huge diversity of ideas that show up while studying graph theory, one that has obtained a lot of popularity is the concept of labelings of graphs. Graph labelings give valuable mathematical models for a wide scope of applications in high technologies (cryptography, astronomy, data security, various coding theory problems, communication networks, etc.). A labeling or a valuation of a graph is any mapping that sends a certain set of graph elements to a certain set of numbers subject to certain conditions. Graph labeling is a mapping of elements of the graph, i.e., vertex and/or edges to a set of numbers (usually positive integers), called labels. If the domain is the vertex-set or the edge-set, the labelings are called vertex labelings or edge labelings respectively. Similarly, if the domain is V (G)[E(G), then the labeling is called total labeling. A reflexive edge irregular k-labeling of graph introduced by Tanna et al.: A total labeling of graph such that for any two different edges ab and a'b' of the graph their weights has ωtχ(ab) = χ(a) + χ(ab) + χ(b) and ωtχ(a'b') = χ(a') + χ(a'b') + χ(b') are distinct. The smallest value of k for which such labeling exist is called the reflexive edge strength of the graph and is denoted by res(G). In this paper we have found the exact value of the reflexive edge irregularity strength of the categorical
product of two paths Pa × Pb for any choice of a ≥ 3 and b ≥ 3. 相似文献
16.
《国际计算机数学杂志》2012,89(4):726-732
A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ′a(G), is the minimum number of colours needed in an avd-colouring of G. It is proved that for any connected 3-colourable Hamiltonian graph G, we have χ′a(G)≤Δ+3. 相似文献
17.
Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a1a2 ... aM andB=b1b2... bN is a list of ordered pairs, (i1,j1), (i2j2), ..., (it,jtt) such that ik < ik+1 and jk < jk+1. In this case the alignmentaligns symbols aik and bjk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log2
P)) algorithm for approximate regular expression matching for an arbitrary and any concavew.
This work was supported in part by the National Institute of Health under Grant RO1 LM04960. 相似文献
18.
Pravin M. Vaidya 《Algorithmica》1989,4(1):569-583
We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL
q,-metric. We give anO((2c
q
)1.5k
–1.5k
((n, n))0.5
n
1.5(logn)2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec
q
=6k
1/q
for theL
q
-metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation. 相似文献
19.
We study a capacitated network design problem with applications in
local access network design. Given a network, the problem is to route
flow from several sources to a sink and to install
capacity on the edges to support the flow at minimum cost.
Capacity can be purchased only in multiples of a fixed quantity.
All the flow from a source must be routed
in a single path to the sink. This NP-hard problem generalizes the
Steiner tree problem and also more effectively models the applications
traditionally formulated as capacitated tree problems. We present
an approximation algorithm with performance ratio
(ST + 2) where ST is the performance ratio of
any approximation algorithm for the minimum Steiner tree problem.
When all sources have unit demand, the ratio
improves to ST + 1) and, in particular, to 2 when all nodes
in the graph are sources. 相似文献
20.
Vida Dujmovic Michael Fellows Michael Hallett Matthew Kitching Giuseppe Liotta Catherine McCartin Naomi Nishimura Prabhakar Ragde Fran Rosamond Matthew Suderman Sue Whitesides David R. Wood 《Algorithmica》2006,45(2):159-182
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-Layer Planarization problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-Layer Planarization problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-Layer Planarization problem in O(k · 6k + |G|) time and the 1-Layer Planarization problem in O(3k · |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems. 相似文献