CINECA IRIS Institutional Research Information System
IRIS è l’archivio della produzione scientifica della Fondazione Bruno Kessler.
EnglishWe 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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte di FBK.
| 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/11582/19569 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11582/19569
Copyright © 2021