作者：
ASANO, TUNIV TOKYO
FAC ENGN DEPT MATH ENGN & INSTRUMENTAT PHYS BUNKYO KU TOKYO 113 JAPAN
For a property π\pi on graphs, the corresponding edge-deletion problem PED(π)P_{{\text{ED}}} (\pi ) (on planar graphs) is stated as follows: given a (planar) graph G, find a set of edges of minimum cardinality whos...
详细信息
We consider a problem of cost-constrained minimum-delay multicasting in a network, which is to find a Steiner tree spanning the source and destination nodes such that the maximum total delay along a path from the sour...
详细信息
We consider a problem of cost-constrained minimum-delay multicasting in a network, which is to find a Steiner tree spanning the source and destination nodes such that the maximum total delay along a path from the source node to a destination node is minimized, while the sum of link costs in the tree is bounded by a constant. The problem is NP-hard even if the network is series-parallel. We present a fully polynomial time approximation scheme for the problem if the network is series-parallel.
The Steiner Forest Problem (SFP for short) is a natural generalization of the classical Steiner Tree Problem. Instead of only one terminal net there is given a set of terminal nets that have to be connected by choosin...
详细信息
The Steiner Forest Problem (SFP for short) is a natural generalization of the classical Steiner Tree Problem. Instead of only one terminal net there is given a set of terminal nets that have to be connected by choosing edges at minimum cost. Richey and Parker [ M.B. Richey, R.G. Parker, On multiple Steiner subgraph problems, Networks 16 (4) (1986) 423-438] posed the question whether SFP is hard on series-parallel graphs. We partially answer this question by showing that SFP is strongly NP-hard on graphs with treewidth 3. On the other hand, a quadratic time algorithm for the special case on outerplanar graphs is suggested. Since series-parallel graphs have treewidth 2 and outerplanar graphs are series-parallel, we almost close the gap between polynomially solvable and hard cases. (C) 2009 Elsevier B. V. All rights reserved.
For positive integers p and q, let G(p,q) be a class of graphs such that vertical bar E(G)vertical bar = 2p. We obtain an upper bound for this sum that is linear in Delta(k-1). These graphs include the planar, 1-plana...
详细信息
For positive integers p and q, let G(p,q) be a class of graphs such that vertical bar E(G)vertical bar <= p vertical bar V(G)vertical bar - q for every G is an element of G(p,q). In this paper, we consider the sum of the kth powers of the degrees of the vertices of a graph G is an element of G(p,q) with Delta(G) >= 2p. We obtain an upper bound for this sum that is linear in Delta(k-1). These graphs include the planar, 1-planar, t-degenerate, outerplanar, and series-parallel graphs.
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive "power" from at most...
详细信息
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive "power" from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P = NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. (C) 2008 Elsevier B.V. All rights reserved.
Given a graphG = (N, E) and a length functionl: E → ?, the graphical Traveling Salesman Problem is that of finding a minimum length cycle goingat least once through each node ofG. This formulation has advantages over...
详细信息
Given a graphG = (N, E) and a length functionl: E → ?, the graphical Traveling Salesman Problem is that of finding a minimum length cycle goingat least once through each node ofG. This formulation has advantages over the traditional formulation where each node must be visited exactly once. We give some facet inducing inequalities of the convex hull of the solutions to that problem. In particular, the so-called comb inequalities of Gr?tschel and Padberg are generalized. Some related integer polyhedra are also investigated. Finally, an efficient algorithm is given whenG is a series-parallel graph.
Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total w...
详细信息
Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an "almost uniform" partition is called an (l, u)- partition. We deal with three problems to find an (l, u)- partition of a given graph;the minimum partition problem is to find an (l, u)- partition with the minimum number of components;the maximum partition problem is defined analogously;and the p-partition problem is to find an (l, u)- partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u(4)n) and the p-partition problem can be solved in time O( p(2)u(4)n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width. (C) 2005 Elsevier B.V. All rights reserved.
For a graph G=(V,E) and a color set C, let f:E -> C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G ...
详细信息
For a graph G=(V,E) and a color set C, let f:E -> C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G have a path in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems with regards to graph diameters, and also characterize these with regards to certain graph classes: cacti, outer planer and series-parallel graphs. We then give FPT algorithms for the three problems on general graphs when parameterized by the number of colors in C;our FPT algorithms imply that all the three problems can be solved in polynomial time for any graph with n vertices if |C|=O(logn).
In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It is known that every planar graph G of n vertices has a...
详细信息
In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It is known that every planar graph G of n vertices has a grid drawing on an (n-2)x(n-2) or (4n/3)x(2n/3) integer grid. In this paper we show that if a planar graph G has a balanced partition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edge-disjoint subgraphs G (1) and G (2), then G has a max {n (1),n (2)}xmax {n (1),n (2)} grid drawing, where n (1) and n (2) are the numbers of vertices in G (1) and G (2), respectively. In particular, we show that every series-parallel graph G has a (2n/3)x(2n/3) grid drawing and a grid drawing with area smaller than 0.3941n (2) (<(2/3)(2) n (2)).
暂无评论