38 citations · 73 across the 6 of their papers we have counts for
8 papers
When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks
Amit Chakrabarti, Lisa Fleischer, Christophe Weibel
Let be a supply graph and a demand graph defined on the same set of vertices. An assignment of capacities to the edges of and demands to the edges of is…
The width of 5-dimensional prismatoids
Benjamin Matschke, Francisco Santos, Christophe Weibel
Santos' construction of counter-examples to the Hirsch Conjecture (2012) is based on the existence of prismatoids of dimension d of width greater than d. Santos, Stephen and Thomas…
Connectivity graphs of uncertainty regions
Erin Chambers, Alejandro Erickson, Sándor Fekete +7
We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which u…
Congestion in planar graphs with demands on faces
Guyslain Naves, Christophe Weibel
We give an algorithm to route a multicommodity flow in a planar graph with congestion , where is the maximum number of terminals on the boundary of a face, when…
Flow-Cut Gaps for Integer and Fractional Multiflows
Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel
Consider a routing problem consisting of a demand graph H and a supply graph G. If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C…
Maximal f-vectors of Minkowski sums of large numbers of polytopes
Christophe Weibel
It is known that in the Minkowski sum of polytopes in dimension , with , the number of vertices of the sum can potentially be as high as the product of the number of ve…
A linear equation for Minkowski sums of polytopes relatively in general position
Komei Fukuda, Christophe Weibel
The objective of this paper is to study a special family of Minkowski sums, that is of polytopes relatively in general position. We show that the maximum number of faces in the sum…
On f-vectors of Minkowski additions of convex polytopes
Komei Fukuda, Christophe Weibel
The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and…