3 papers
math.OC2018
Robust capacitated trees and networks with uniform demands
Cédric Bentz, Marie-Christine Costa, Pierre-Louis Poirion +1
We are interested in the design of robust (or resilient) capacitated rooted Steiner networks in case of terminals with uniform demands. Formally, we are given a graph, capacity and…
cs.DM2017
Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees
Cédric Bentz
For a fixed number of colors, we show that, in node-weighted split graphs, cographs, and graphs of bounded tree-width, one can determine in polynomial time whether a proper list-co…
cs.DS2017
An FPT algorithm for planar multicuts with sources and sinks on the outer face
Cédric Bentz
Given a list of k source-sink pairs in an edge-weighted graph G, the minimum multicut problem consists in selecting a set of edges of minimum total weight in G, such that removing…