We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynormally solvable. We exhibit a good characterization for this problem in the form of a min-max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler's problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose.
Titolo: | Covering partially directed graphs with directed paths | |
Autori: | ||
Data di pubblicazione: | 2006 | |
Rivista: | ||
Abstract: | We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynormally solvable. We exhibit a good characterization for this problem in the form of a min-max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler's problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose. | |
Handle: | http://hdl.handle.net/11562/409572 | |
Appare nelle tipologie: | 01.01 Articolo in Rivista |