In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node rea...
详细信息
In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series-parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(nm+m log m) time, where m is the number of arcs, and a dynamic programming algorithm with running time O(m log m). For the integral version of the problem, which is known to be N P-complete, we present a pseudo-polynomial algorithm. (C) 2013 Elsevier B.V. All rights reserved.
It has been known that every planar 4-graph has a 2-bend 2-D orthogonal drawing, with the only exception being the octahedron, every planar 3-graph has a 1-bend 2-D orthogonal drawing with the only exception being K(4...
详细信息
It has been known that every planar 4-graph has a 2-bend 2-D orthogonal drawing, with the only exception being the octahedron, every planar 3-graph has a 1-bend 2-D orthogonal drawing with the only exception being K(4), and every outerplanar 3-graph with no triangles has a 0-bend 2-D orthogonal drawing. We show in this paper that every series-parallel 4-graph has a 1-bend 2-D orthogonal drawing. (C) 2009 Elsevier B.V. All rights reserved.
We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow Lambda lie in the disc vertical bar q - 1 vertical bar = 3, we exhibit a family of graphs, namely, the "leaf-joined t...
详细信息
We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow Lambda lie in the disc vertical bar q - 1 vertical bar < (Lambda - 1)/log 2. More generally, the same bound holds for the (real or complex) roots of the multivariate Tutte polynomial when the edge weights lie in the "real antiferromagnetic regime" -1 <= v(e) <= 0. For each Lambda >= 3, we exhibit a family of graphs, namely, the "leaf-joined trees", with maxmaxflow. and chromatic roots accumulating densely on the circle vertical bar q - 1 vertical bar = Lambda - 1, thereby showing that our result is within a factor 1/log 2 approximate to 1.442695 of being sharp.
series-parallel graphs are known to be precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone, the T-join polytope, the cut polytope, the multicut polytope and the T-join do...
详细信息
series-parallel graphs are known to be precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone, the T-join polytope, the cut polytope, the multicut polytope and the T-join dominant are TDI. We prove that these systems are actually box-TDI. As a byproduct, our result yields a min-max relation for a new problem: the trader multiflow problem. The latter generalizes both the maximum multiflow and min-cost multiflow problems and we show that it is polynomial-time solvable in series-parallel graphs. (C) 2018 Elsevier B.V. All rights reserved.
A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each ...
详细信息
A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)| >= min{5, triangle + 1} for each vertex v and |L(e)| >= max{5, d(v) + 1, d(w) + 1} for each edge e = vw, where triangle is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with triangle + 1 colors if triangle >= 4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition. (C) 2004 Elsevier B. V. All rights reserved.
Let c(n) be themaximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)(1/n) exists and equals beta = 1.502837 ..., where beta is a constant related to the recurrence x(n+1) = 1 + x(n)(2...
详细信息
Let c(n) be themaximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)(1/n) exists and equals beta = 1.502837 ..., where beta is a constant related to the recurrence x(n+1) = 1 + x(n)(2), x(0) = 1. The same result holds for the larger class of series-parallel graphs.
The st-bond polytope of a graph is the convex hull of the incidence vectors of its st-bonds, where an st-bond is a minimal st-cut. In this paper, we provide a linear description of the st-bond polytope on series-paral...
详细信息
The st-bond polytope of a graph is the convex hull of the incidence vectors of its st-bonds, where an st-bond is a minimal st-cut. In this paper, we provide a linear description of the st-bond polytope on series-parallel graphs. We also show that the st-bond polytope is the intersection of the st-cut dominant and the bond polytope.
In this paper, we consider the weighted perfect domination problem in series-parallel graphs. Suppose G = (V, E) is a graph in which every vertex x is-an-element-of V has a cost c(x) and every edge e is-an-element-of ...
详细信息
In this paper, we consider the weighted perfect domination problem in series-parallel graphs. Suppose G = (V, E) is a graph in which every vertex x is-an-element-of V has a cost c(x) and every edge e is-an-element-of E has a cost c(e). The weighted perfect domination problem is to find a subset D subset-of V such that every vertex not in D is adjacent to exactly one vertex in D and its total cost c(D) = SIGMA{c(x): x is-an-element-of D} + SIGMA{c(x, y): x is-not-an-element-of D, y is-an-element-of D and (x, y) is-an-element-of E} is minimum. This problem is NP-complete for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for the problem in series-parallel graphs.
A series-parallel graph can be constructed from a certain graph by recurslvely applying “series” and “parallel” connections The class of such graphs, which Is a well-known model of series-parallel electrical netwo...
详细信息
We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the ...
详细信息
We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. Note that the class of generalized series-parallel graphs includes all outerplanar graphs. We can perform the counting in time O (m Delta(3)), where Delta is the maximum degree of the graph with m edges. We use O (mn Delta(2) log Delta) bits to store intermediate values during our computations. To date, these are the first known polynomial-time algorithms to count or sample ETs of any class of graphs;there are no other known polynomial-time algorithms to even approximately count or sample ETs of any other class of graphs. The problem of counting ETs is known to be # P-complete for general graphs (Brightwell and Winkler, 2005 [2]) also for planar graphs (Creed, 2010 [3]). (C) 2011 Elsevier B.V. All rights reserved.
暂无评论