Thumbnail
Access Restriction
Open

Author Chekuri, Chandra
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Flow-cut Gap ♦ Fractional Multiflows ♦ Minimum Value ♦ Minor-free Graph ♦ Several Technical Tool ♦ Routing Problem Instance Consisting ♦ Supply Graph ♦ Edge St ♦ Non-trivial Special Class ♦ Demand Graph ♦ Primal Method ♦ Graph K2 ♦ Successful Metric Embeddings Approach ♦ Feasible Multiflow ♦ Fractional Flow-cut Gap ♦ Integer Flow-cut Gap ♦ Cut Condition ♦ Well-known Conjecture ♦ Series-parallel Operation ♦ Feasible Integer
Abstract Consider a routing problem instance consisting of a demand graph H = (V, E(H)) and a supply graph G = (V, E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is wellknown that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K2,3. In this paper we are primarily interested in the “integer ” flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) [15] to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the “primal ” method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: • Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2012-01-01