共查询到20条相似文献,搜索用时 109 毫秒
1.
Let P
G
(s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A detour at a node u∈P
G
(s,t)=(s,…,u,v,…,t) is defined as a shortest path P
G−e
(u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e=(u,v)∈P
G
(s,t) whose removal produces a detour at node u such that the ratio of the length of P
G−e
(u,t) to the length of P
G
(u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved
in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks
are shown.
This research is supported by NSF of China under Grants 70471035, 70525004, 701210001 and 60736027, and PSF of China under
Grant 20060401003. 相似文献
2.
Finding an anti-risk path between two nodes in undirected graphs 总被引:1,自引:0,他引:1
Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent
site of the blocked edge. Let ℘={P
G
(s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper
will propose the Anti-risk Path Problem of finding a path P
G
(s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n
2log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively.
This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of
China under Grant 20060401003. 相似文献
3.
A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity λ
c
(G) is the cardinality of a minimum cyclic edge-cut of G. We call a graph super cyclically edge-connected, if the removal of any minimum cyclic edge-cut results in a component which
is a shortest cycle. In this paper, we show that a connected vertex-transitive or edge-transitive graph is super cyclically
edge-connected if either G is cubic with girth g(G)≥7, or G has minimum degree δ(G)≥4 and girth g(G)≥6. 相似文献
4.
For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let
G
(V – s) denote min{c
G(X) | Ø X V – s}, where c
G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e
1 and e
2 incident to s is called (k, s)-feasible if G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k
G
(V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n
3 log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n
3 log n) time. 相似文献
5.
Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted
version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen
these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the
set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm
for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within
a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time. 相似文献
6.
Mathieu Bouchard Alain Hertz Guy Desaulniers 《Journal of Combinatorial Optimization》2009,17(2):168-191
An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S
v
(G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D
v
(G,c) the minimum number of integers which must be added to S
v
(G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑
v∈V
D
v
(G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds
on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a
tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them
having a known optimal deficiency. 相似文献
7.
O. Favaron H. Karami R. Khoeilar S. M. Sheikholeslami 《Journal of Combinatorial Optimization》2010,20(1):76-84
A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number
γ
t
(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number
sdgt(G)\mathrm {sd}_{\gamma_{t}}(G)
is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that
sdgt(G) £ gt(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1
for some classes of graphs. 相似文献
8.
For a weighted 2-edge connected graph G=(V,E), we are to find a “minimum risk path” from source s to destination t. This is a shortest s?t path under the assumption that at most one edge on the path may be blocked. The fact that the edge is blocked is known only when we reach a site adjacent to the blocked edge. If n and m are the number of nodes and edges of G, then we show that this problem can be solved in O(n 2) time using only simple data structures. This is an improvement over the previous O(mn+n 2logn) time algorithm. Moreover, with use of more complicated data structures like Fibonacci Heaps and transmuters the time can be further reduced to O(m+nlogn). 相似文献
9.
We study the polyhedron P(G) defined by the convex hull of 2-edge-connected subgraphs of G where multiple copies of edges may be chosen. We show that each vertex of P(G) is also a vertex of the LP relaxation. Given the close relationship with the Graphical Traveling Salesman problem (GTSP), we examine how polyhedral results for GTSP can be modified and applied to P(G). We characterize graphs for which P(G) is integral and study how this relates to a similar result for GTSP. In addition, we show how one can modify some classes of valid inequalities for GTSP and produce new valid inequalities and facets for P(G). 相似文献
10.
Cheng-Hsiao Tsou Gen-Huey Chen Hung-I Yu Ching-Chi Lin 《Journal of Combinatorial Optimization》2013,25(4):602-616
We propose the problem of finding broadcast medians in heterogeneous networks. A heterogeneous network is represented by a graph G=(V,E), in which each edge has a weight that denotes the communication time between its two end vertices. The overall delay of a vertex v∈V(G), denoted as b(v,G), is the minimum sum of the communication time required to send a message from v to all vertices in G. The broadcast median problem consists of finding the set of vertices v∈V(G) with minimum overall delay b(v,G) and determining the value of b(v,G). In this paper, we consider the broadcast median problem following the heterogeneous postal model. Assuming that the underlying graph G is a general graph, we show that computing b(v,G) for an arbitrary vertex v∈V(G) is NP-hard. On the other hand, assuming that G is a tree, we propose a linear time algorithm for the broadcast median problem in heterogeneous postal model. 相似文献
11.
Carlos J. Luz 《Journal of Combinatorial Optimization》2011,22(4):882-894
This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by α
k
(G). From a well known Motzkin-Straus result, a relationship is deduced between α
k
(G) and the independence number α(G). Next, it is proved that the upper bounds υ
k
(G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455–463, 2007) can easily be computed from υ
0(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above
paper. The paper continues with the introduction of a new upper bound on α
k
(G) improving υ
k
(G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational
experiments which were performed to compare all bounds studied are reported. 相似文献
12.
Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all
vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive
the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application
of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability
of this problem and prove Ω(g1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds.
Supported in part by the NSF of China under Grant No. 70221001 and 60373012. 相似文献
13.
Given a graph G=(V,E) with node weight w:V→R
+ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard
and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n
O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a
polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs.
As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial
time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs. 相似文献
14.
For a graph G with vertex set V and edge set E, a (k,k′)-total list assignment L of G assigns to each vertex v a set L(v) of k real numbers as permissible weights, and assigns to each edge e a set L(e) of k′ real numbers as permissible weights. If for any (k,k′)-total list assignment L of G, there exists a mapping f:V∪E→? such that f(y)∈L(y) for each y∈V∪E, and for any two adjacent vertices u and v, ∑ y∈N(u) f(uy)+f(u)≠∑ x∈N(v) f(vx)+f(v), then G is (k,k′)-total weight choosable. It is conjectured by Wong and Zhu that every graph is (2,2)-total weight choosable, and every graph with no isolated edges is (1,3)-total weight choosable. In this paper, it is proven that a graph G obtained from any loopless graph H by subdividing each edge with at least one vertex is (1,3)-total weight choosable and (2,2)-total weight choosable. It is shown that s-degenerate graphs (with s≥2) are (1,2s)-total weight choosable. Hence planar graphs are (1,10)-total weight choosable, and outerplanar graphs are (1,4)-total weight choosable. We also give a combinatorial proof that wheels are (2,2)-total weight choosable, as well as (1,3)-total weight choosable. 相似文献
15.
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of
labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label
s
–
t
path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms
and hardness results for MinLST and MinLP. 相似文献
16.
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr(G)≤4n/5 if δ=1 and n≥3, Γpr(G)≤3n/4 if δ=2 and n≥6, and Γpr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γpr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γpr(G)=3n/4 are characterized. 相似文献
17.
It is well known that if G is a multigraph then χ′(G)≥χ′*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(G[U])|/(|U|−1):U⊆V(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′*(G)+c
χ′*(G) when χ′*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋; and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with
$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor
, improving the above mentioned results. As a consequence, for multigraphs G with
$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}
the answer to a 1964 problem of Vizing is in the affirmative. 相似文献
18.
This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log 2
e(G)⌉≤t(G)≤⌈log 2
e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that
the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite
graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤24 or
for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤25 or
for k≥6.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013.
G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical
Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office. 相似文献
19.
On backbone coloring of graphs 总被引:1,自引:0,他引:1
Weifan Wang Yuehua Bu Micka?l Montassier André Raspaud 《Journal of Combinatorial Optimization》2012,23(1):79-93
Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum
average degree, graphs with maximum degree 3, etc. 相似文献
20.
For a permutation f of the vertex set V(G) of a connected graph G, let δ
f
(x,y)=|d(x,y)−d(f(x),f(y))|. Define the displacement δ
f
(G) of G with respect to f to be the sum of δ
f
(x,y) over all unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ
f
(G) among the n! permutations f of V(G). In this note, we determine all trees T with π(T)=2 or 4.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. 相似文献