Callcc/Guyslain/Works/tableau

Version & licenses
Creative Commons License
  1. {`frametitle "The Disjoint Paths Problems"}
  2. {`windowtitle "The Disjoint Paths Problems: an annotated tableau"}
  3. {`menu "guyslain"}
  4. {`leftpicture af://guyslain/images/maths/disjoint_paths_vertical.png}


  5. {section 2 {`anchor "preliminary"} {`center} Preliminary}

  6. This page is the online version of the tableau {ref "multiflowtableau2008"}, a joint work with {link http://www.g-scop.inpg.fr/~seboa/ András Sebő}, that appeared in the book {emph Research Trends in Combinatorial Optimization} {ref "researchtrends"}. It is an attempt to capture some of the most important variants of the disjoint paths problems, as well as pointing out some open problems. We only considered the decision versions of the problems. We believe that an optimization version of the tableau, including approximability, would also be necessary.

  7. Despite all our care in making this tableau, it is still possible that we missed some known results. If you find any error or omission, or have any constructive remark, it would be most helpful to send me an email.

  8. The main definitions concerning disjoint paths problems, and the notations can be found on {link af://callcc/Guyslain/Works/disjoint_paths this page}.

  9. The tableau is divided into three parts:
  10. - {internal "arb" the supply graph $G$ is arbitrary.}
  11. - {internal "Gplan" the supply graph $G$ is restricted to be planar.}
  12. - {internal "GHplan" the graph $G+H$ of supplies and demands is restricted to be planar.}

  13. Each part is then further divided between the undirected, directed and directed acyclic cases, and depending on the nature of $H$ and the quantity of request. You will find a {internal "biblio" bibliography} at the foot of this page.

  14. {section 2 {`anchor "arb"} {`center} $G$ is arbitrary}

  15. {array 12 11 {`head 3} {`rborderbot [5 8]}
  16. {{`rowspan 2} {`colspan 2} } {{`colspan 3} {`tooltip "G and H are directed"} directed} {{`colspan 3} {`tooltip "G and H are directed, G is acyclic"} directed acyclic} {{`colspan 3} {`tooltip "G and H are undirected"} undirected}
  17. {{`colspan 2} {`tooltip "arc-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d} {{`colspan 2} {`tooltip "arc-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d} {{`colspan 2} {`tooltip "edge-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d}
  18. {{`tooltip "number of commodities"} $|H|$} {{`tooltip "encoding (constant, unary, binary) of the capacities and requests."} $r$}
  19. {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$} {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$} {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$}
  20. {{`rowspan 2} {`tooltip "No bound on the number of commodities."} arb.}
  21. {{`tooltip "Capacities are encoded in binary."} bin}
  22. {sc NPC}
  23. {sc NPC}
  24. {{`rowspan 2} {sc NPC}}
  25. {sc NPC} {sc NPC}
  26. {{`rowspan 2}
  27. {sc NPC}}
  28. {sc NPC}
  29. {sc NPC}
  30. {{`rowspan 2} {internal "rs" {sc NPC}}}
  31. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  32. {sc NPC}
  33. {sc NPC}
  34. {sc NPC}
  35. {sc NPC}
  36. {sc NPC}
  37. {sc NPC}
  38. {{`rowspan 3} {`tooltip "The number of commodity is a constant."} fix}
  39. {{`tooltip "Capacities are encoded in binary."} bin}
  40. {sc NPC}
  41. {sc NPC}
  42. {{`rowspan 3} {sc NPC}}
  43. {sc NPC} {sc NPC}
  44. {{`rowspan 3} {internal "fhw2" {`tooltip "By usual reduction to arc-disjoint"} {sc P}}}
  45. {sc NPC}
  46. {sc NPC}
  47. {{`rowspan 3} {internal "rs" {sc P}}}
  48. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  49. {sc NPC}
  50. {sc NPC}
  51. {sc NPC}
  52. {{internal "vygen" {sc NPC}} {*ref "vygen1995ncs"*}}
  53. {sc NPC}
  54. {{internal "vygen" {`tooltip "Using Vygen's reduction from directed acyclic"} {sc NPC}}}
  55. {{`tooltip "The total number of requested paths is a constant."} fix}
  56. {sc NPC}
  57. {{internal "ip" ???} {*ref "ibaraki1991wtl"*}}
  58. {{internal "fhw2" {sc P}} {*ref "ForHopWyl80"*}}
  59. {sc P }
  60. {{`tooltip "Reduction to vertex-disjoint case"} {sc P }}
  61. {{internal "lomon" {sc P }} {*ref "lomonosov1985cam *}}
  62. {{`rowspan 4} {`tooltip "Only two commodities"} 2}
  63. {{`tooltip "Capacities are encoded in binary."} bin}
  64. {sc NPC}
  65. {{internal "frank" {sc P }} {*ref "Frank89"*}}
  66. {{`rowspan 4} {internal "fhw" {sc NPC}} {*ref "ForHopWyl80"*}}
  67. {sc NPC}
  68. {sc P }
  69. {{`rowspan 4} {sc P}}
  70. {sc NPC }
  71. {{`tooltip "Rothschild and Whinston"} {sc P }}
  72. {{`rowspan 4} {sc P}}
  73. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  74. {sc NPC}
  75. {sc P }
  76. {{internal "eis" {sc NPC}} {*ref "vygen1995ncs"*}}
  77. {sc P }
  78. {sc NPC}
  79. {sc P }
  80. {{`tooltip "The total number of requested paths is a constant."} fix}
  81. {sc NPC}
  82. {sc P }
  83. {sc P }
  84. {sc P }
  85. {sc NPC}
  86. {sc P }
  87. {{`tooltip "The very restricted case when we look for only two disjoint paths"} 2}
  88. {{internal "fhw" {sc NPC}} {*ref "ForHopWyl80"*}}
  89. {sc P }
  90. {sc P }
  91. {sc P }
  92. {sc P }
  93. {sc P }
  94. }

  95. A remarkable fact is that here only one cell is open, namely the arc-disjoint paths problem for Eulerian instances with a fixed total request and $|E(H)| \geq 3$. The simplest version is actually in {sc P}, where one wants to decide the existence of three disjoint paths, as asserted by the Theorem {ref "ip"} of Ibaraki and Poljak stated below. If the total request is $4$ the problem is open.

  96. The main theorems, in an arbitrary order:

  97. {theorem {`anchor "eis"} {`caption {Even, Itai, Shamir {ref "eis76"}}} {
  98. The edge-disjoint paths problem in undirected graphs and the arc-disjoint paths problem in directed acyclic graphs is NP-complete,, even if $r(E(H)) = 3$.
  99. }}

  100. {theorem {`anchor "fhw"} {`caption {Fortune, Hopcroft, Wyllie {ref "ForHopWyl80"}}} {
  101. The vertex-disjoint paths problem is {sc NP}-complete, even if $r(E(H)) = 2$.
  102. }}

  103. {theorem {`anchor "vygen"} {`caption {Vygen {ref "vygen1995ncs"}}} {
  104. The integer multicommodity flow problem is {sc NP}-complete even if $G$ is an acyclic directed graph, $r+c$ is Eulerian and $|E(H)| = 3$.
  105. }}

  106. {theorem {`anchor "frank"} {`caption {Frank {ref "Frank89"}}} {
  107. The integer multicommodity flow problem in Eulerian digraphs with $|E(H)| = 2$ is solvable in polynomial-time. The cut condition is sufficient for the existence of a solution.
  108. }}

  109. {theorem {`anchor "fhw2"} {`caption {Fortune, Hopcroft, Wyllie {ref "ForHopWyl80"}}} {
  110. The arc-disjoint paths problem in directed acyclic graph with $r(E(H))$ bounded is solvable in polynomial-time.
  111. }}

  112. {theorem {`anchor "lomon"} {`caption {Lomonosov {ref "lomonosov1985cam"}}} {
  113. The undirected integer multicommodity flow problem is solvable in polynomial-time in Eulerian instances when $H$ is the union of two stars, or $K_4$, or $C_5$. In these cases, the cut condition is sufficient.
  114. }}

  115. A weaker version of the previous theorem was proved by Rothschild and Whinston {ref "rothschild1966ftc"} for the case when $H$ is the union of two stars.

  116. {theorem {`anchor "rs"} {`caption {Robertson, Seymour {ref "robertson1995gmx"}}} {
  117. The vertex-disjoint paths problem in undirected graphs with $r(E(H))$ bounded is solvable in polynomial-time. By usual reduction, under the same condition the edge-disjoint paths problem is also in {sc P}.
  118. }}

  119. {theorem {`anchor "ip"} {`caption {Ibaraki, Poljak {ref "ibaraki1991wtl"}}} {
  120. The arc-disjoint paths problem in Eulerian instances with $r(E(H)) = 3$ is in {sc P}.
  121. }}

  122. The following powerful lemma from Vygen allows to extend some results from DAG to undirected graphs when the Eulerian condition is assumed. It is used several times in the tableau.

  123. {lemma {`anchor "vred"} {`caption {Vygen {ref "vygen1995ncs"}}} {
  124. Let $G,H,r,c$ be an instance of the arc-disjoint paths problem with $G+H$ Eulerian and $G$ acyclic. Let $G',H'$ be obtained by neglecting the orientation of $G,H$ respectively. There is a solution to the arc-disjoint paths problem in $G,H,r,c$ iff there is a solution to the edge-disjoint paths problem in $G',H',r,c$.
  125. }}


  126. {section 2 {`anchor "Gplan"} {`center} $G$ is planar}

  127. {array 12 11 {`head 3} {`rborderbot [5 8]}
  128. {{`rowspan 2} {`colspan 2} } {{`colspan 3} {`tooltip "G and H are directed"} directed} {{`colspan 3} {`tooltip "G and H are directed, G is acyclic"} directed acyclic} {{`colspan 3} {`tooltip "G and H are undirected"} undirected}
  129. {{`colspan 2} {`tooltip "arc-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d} {{`colspan 2} {`tooltip "arc-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d} {{`colspan 2} {`tooltip "edge-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d}
  130. {{`tooltip "number of commodities"} $|H|$} {{`tooltip "encoding (constant, unary, binary) of the capacities and requests."} $r$}
  131. {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$} {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$} {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$}
  132. {{`rowspan 2} {`tooltip "No bound on the number of commodities."} arb.}
  133. {{`tooltip "Capacities are encoded in binary."} bin}
  134. {sc NPC}
  135. {sc NPC}
  136. {{`rowspan 2} {sc NPC}}
  137. {sc NPC}
  138. {sc NPC}
  139. {{`rowspan 2} {sc NPC}}
  140. {sc NPC}
  141. {sc NPC}
  142. {{`rowspan 2} {sc NPC}}
  143. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  144. {sc NPC}
  145. {sc NPC}
  146. {sc NPC}
  147. {internal "marx" {sc NPC}}
  148. {sc NPC}
  149. {sc NPC}
  150. {{`rowspan 3} {`tooltip "The number of commodity is a constant."} fix}
  151. {{`tooltip "Capacities are encoded in binary."} bin}
  152. {sc NPC}
  153. { ??? }
  154. {{`rowspan 3} {internal "schr" {sc P }}}
  155. {sc NPC} { ??? }
  156. {{`rowspan 3} {sc P }}
  157. {sc NPC}
  158. { ??? }
  159. {{`rowspan 3} {sc P }}
  160. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  161. {sc NPC}
  162. { ??? }
  163. {{`tooltip "Proved by Schwärzler first for three demand edges"} {sc NPC}}
  164. {internal "nav2" {sc P}}
  165. {{`tooltip "Proved by Schwärzler first for three demand edges"} {sc NPC}}
  166. { ??? }
  167. {{`tooltip "The total number of requested paths is a constant."} fix}
  168. { ??? }
  169. { ??? }
  170. {sc P }
  171. {sc P }
  172. {sc P }
  173. {sc P }
  174. {{`rowspan 4} {`tooltip "Only two commodities"} 2}
  175. {{`tooltip "Capacities are encoded in binary."} bin}
  176. {sc NPC}
  177. {sc P }
  178. {{`rowspan 4} {sc P }}
  179. {sc NPC}
  180. {sc P }
  181. {{`rowspan 4} {sc P }}
  182. {sc NPC}
  183. {sc P }
  184. {{`rowspan 4} {sc P }}
  185. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  186. {{`tooltip "First proved by Dirk Müller, see below."} {sc NPC}}
  187. {sc P }
  188. {internal "naves" {sc NPC}}
  189. {sc P }
  190. {internal "naves" {sc NPC}}
  191. {sc P }
  192. {{`tooltip "The total number of requested paths is a constant."} fix}
  193. { ??? }
  194. {sc P }
  195. {sc P }
  196. {sc P }
  197. {sc P }
  198. {sc P }
  199. {{`tooltip "The very restricted case when we look for only two disjoint paths"} 2}
  200. { ??? }
  201. {sc P }
  202. {sc P }
  203. {sc P }
  204. {sc P }
  205. {sc P }
  206. }

  207. {theorem {`anchor "marx"} {`caption {Marx {ref "marx2004edp"}}} {
  208. The arc-disjoint paths problem is {sc NP}-complete on Eulerian instances even if $G$ is planar and acyclic. The edge-disjoint paths problem is {sc NP}-complete on Eulerian instances even if $G$ is undirected and planar.
  209. }}

  210. {theorem {`anchor "naves"} {`caption {Naves {ref "mpa2pairs2010"}}} {
  211. The integer multicommodity flow problem is {sc NP}-complete even with one of the following restrictions:
  212. - $G$ is a planar undirected graph, $H$ has only two edges with endpoints on the same face of $G$,
  213. - $G$ is a directed graph, $G+H$ is planar and $|V(H)| = 2$,
  214. - $G$ is a directed acyclic planar graph, $H$ has only two arcs with endpoints on the same face of $G$.
  215. }}

  216. Dirk Müller {ref "muller2006cpd"} proved in 2006 the weaker case when $G$ is directed and planar and $|V(H)| = 2$.

  217. {theorem {`anchor "schr"} {`caption {Schrijver {ref "schrijver1994fkd"}}} {
  218. The vertex-disjoint paths problem in planar digraphs with $|E(H)|$ bounded is solvable in polynomial-time.
  219. }}

  220. {theorem {`anchor "nav2"} {`caption {Naves {ref "dpathsplanar2010"}}} {
  221. The edge-disjoint paths problem is solvable in polynomial-time on Eulerian instances when $G$ is a directed acyclic planar graph and $|E(H)|$ is bounded.
  222. }}


  223. {section 2 {`anchor "GHplan"} {`center} $G+H$ is planar}

  224. {array 12 11 {`head 3} {`rborderbot [5 8]}
  225. {{`rowspan 2} {`colspan 2} } {{`colspan 3} {`tooltip "G and H are directed"} directed} {{`colspan 3} {`tooltip "G and H are directed, G is acyclic"} directed acyclic} {{`colspan 3} {`tooltip "G and H are undirected"} undirected}
  226. {{`colspan 2} {`tooltip "arc-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d} {{`colspan 2} {`tooltip "arc-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d} {{`colspan 2} {`tooltip "edge-disjoint paths"} $E$-d} {{`rowspan 2} {`tooltip "vertex-disjoint paths"} $V$-d}
  227. {{`tooltip "number of commodities"} $|H|$} {{`tooltip "encoding (constant, unary, binary) of the capacities and requests."} $r$}
  228. {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$} {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$} {{`tooltip "No other requirement."} $gen$} {{`tooltip "G+H is Eulerian"} $Eul$}
  229. {{`rowspan 2} {`tooltip "No bound on the number of commodities."} arb.}
  230. {{`tooltip "Capacities are encoded in binary."} bin}
  231. {sc NPC}
  232. { ??? }
  233. {{`rowspan 2} {sc NPC}}
  234. {internal "ly" {sc P }}
  235. {sc P }
  236. {{`rowspan 2} {internal "mp_tableau" {sc NPC}}}
  237. {sc NPC}
  238. {internal "seym" {sc P }}
  239. {{`rowspan 2} {internal "mp" {sc NPC}}}
  240. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  241. {sc NPC}
  242. { ??? }
  243. {sc P }
  244. {sc P }
  245. {internal "mp" {sc NPC}}
  246. {sc P }
  247. {{`rowspan 3} {`tooltip "The number of commodity is a constant."} fix}
  248. {{`tooltip "Capacities are encoded in binary."} bin}
  249. {sc NPC}
  250. { ??? }
  251. {{`rowspan 3} {sc P }}
  252. {sc P }
  253. {sc P }
  254. {{`rowspan 3} {sc P }}
  255. {internal "sebo" {sc P }}
  256. {sc P }
  257. {{`rowspan 3} {sc P }}
  258. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  259. {sc NPC}
  260. { ??? }
  261. {sc P }
  262. {sc P }
  263. {sc P }
  264. {sc P }
  265. {{`tooltip "The total number of requested paths is a constant."} fix}
  266. { ??? }
  267. { ??? }
  268. {sc P }
  269. {sc P }
  270. {sc P }
  271. {sc P }
  272. {{`rowspan 4} {`tooltip "Only two commodities"} 2}
  273. {{`tooltip "Capacities are encoded in binary."} bin}
  274. {sc NPC}
  275. {sc P }
  276. {{`rowspan 4} {sc P }}
  277. {sc P }
  278. {sc P }
  279. {{`rowspan 4} {sc P }}
  280. {sc P }
  281. {sc P }
  282. {{`rowspan 4} {sc P }}
  283. {{`tooltip "capacities are encoded in unary, or equivalently by using parallel arcs or edges."} un}
  284. {internal "nav2" {sc NPC}}
  285. {sc P }
  286. {sc P }
  287. {sc P }
  288. {sc P }
  289. {sc P }
  290. {{`tooltip "The total number of requested paths is a constant."} fix}
  291. { ??? }
  292. {sc P }
  293. {sc P }
  294. {sc P }
  295. {sc P }
  296. {sc P }
  297. {{`tooltip "The very restricted case when we look for only two disjoint paths"} 2}
  298. { ??? }
  299. {sc P }
  300. {sc P }
  301. {sc P }
  302. {sc P }
  303. {sc P }
  304. }


  305. {theorem {`anchor "mp"} {`caption {Middendorf, Pfeiffer {ref "middendorf1993cdp"}}} {
  306. The edge-disjoint paths problem is {sc NP}-complete even if $G+H$ is planar.
  307. }}

  308. From the previous theorem, we derived a directed version:

  309. {theorem {`anchor "mp_tableau"} {`caption {Naves, Sebő {ref "multiflowtableau2008"}}} {
  310. The vertex-disjoint paths problem in acyclic digraphs with $G+H$ planar is NP-complete.
  311. }}

  312. {theorem {`anchor "ly"} {`caption {Lucchesi, Younger {ref "lucchesi1978mtd"}}} {
  313. The integer multicommodity flow problem is in {sc P} when restricted to instances where $G$ is a directed acyclic graph and $G+H$ is planar.
  314. }}

  315. {theorem {`anchor "seym"} {`caption {Seymour {ref "seymour1981oca"}}} {
  316. The integer multicommodity flow problem is in {sc P} when restricted to Eulerian instances where $G$ is undirected and $G+H$ does not contain a $K_5$-minor (in particular when $G+H$ is planar).
  317. }}

  318. {theorem {`anchor "sebo"} {`caption {Sebő {ref "sebHo1993ipm"}}} {
  319. The integer multicommodity flow problem is in {sc P} when $G$ is undirected, $G+H$ is planar and $|E(H)|$ is bounded.
  320. }}


  321. {internal "preliminary" Back to the top.}

  322. {section 2 {`anchor "biblio"} Bibliography}

  323. {publi {:

  324. @book{schrijver1990pfa,
  325. title= "Paths, Flows, and VLSI-Layout",
  326. editor= "Alexander Schrijver",
  327. editor= "László Lovász",
  328. editor= "Bernhard Korte",
  329. editor= "Hans Jürgen Promel",
  330. editor= "Ronald L. Graham",
  331. year= 1990,
  332. publisher= "Springer-Verlag New York, Inc. Secaucus, NJ, USA"
  333. }

  334. @book{researchtrends,
  335. title= "Research Trends in Combinatorial Optimization",
  336. editor= "William J. Cook",
  337. editor= "László Lovász",
  338. editor= "Jens Vygen",
  339. year= 2008,
  340. publisher= "Springer Verlag"
  341. }

  342. @article{costa2005mma,
  343. title= "Minimal multicut and maximal integer multiflow: a survey",
  344. author= "Marie-Christine Costa",
  345. author= "Lucas Létocart",
  346. author= "Frédéric Roupin",
  347. journal= "European Journal of Operational Research",
  348. volume= 162,
  349. number= 1,
  350. pages= 55--69,
  351. year= 2005,
  352. publisher= "Elsevier"
  353. }

  354. @article{eis76,
  355. author = "Shimon Even",
  356. author = "Alon Itai",
  357. author = "Adi Shamir",
  358. title = "On the Complexity of Timetable and Multicommodity Flow Problems",
  359. journal = "SIAM Journal on Computing",
  360. year = 1976,
  361. volume = 5,
  362. number = 4,
  363. pages = 691--703
  364. }

  365. @article{ForHopWyl80,
  366. author = "Steven Fortune",
  367. author = "John E. Hopcroft",
  368. author = "James Wyllie",
  369. title = "The Directed Subgraph Homeomorphism Problem",
  370. journal = "TCS: Theoretical Computer Science",
  371. volume = 10,
  372. year = 1980
  373. }

  374. @article{frank1985edp,
  375. title= "Edge-disjoint paths in planar graphs",
  376. author= "András Frank",
  377. journal= "Journal of combinatorial theory. Series B",
  378. volume= 39,
  379. number= 2,
  380. pages= 164--178,
  381. year= 1985,
  382. publisher= "Academic Press"
  383. }

  384. @article{Frank89,
  385. author = "András Frank",
  386. title = "On Connectivity Properties of Eulerian Digraphs",
  387. journal = "Annals of Discrete Mathematics",
  388. year = 1989,
  389. volume = 41,
  390. pages = 179--194
  391. }

  392. @article{Frank90a,
  393. author = "András Frank",
  394. title = "Packing paths in planar graphs",
  395. journal = "Combinatorica",
  396. pages = 325--331,
  397. year = 1990,
  398. volume = 10,
  399. publisher = "Akadémiai Kiadó"
  400. }

  401. @inbook{frank90ppc,
  402. author = "András Frank",
  403. editor = "Bernhard Korte",
  404. editor = "László Lovász",
  405. editor = "Hans Jürgen Prőmel",
  406. editor = "Alexander Schrijver",
  407. publisher = "Springer",
  408. title = "Packing paths, circuits and flows",
  409. booktitle = "Paths, Flows and VLSI Layouts",
  410. year = 1990,
  411. pages = 47--100
  412. }

  413. @article{frank1984cda,
  414. title= "Covering directed and odd cuts",
  415. author= "András Frank",
  416. author= "Éva Tardos",
  417. author = "András Sebő",
  418. journal= "Mathematical Programming study 22",
  419. pages= 99-112,
  420. year= 1984,
  421. publisher= "North-Holland"
  422. }

  423. @article{geelen2002packing,
  424. title= "Packing odd circuits in Eulerian graphs",
  425. author= "Jim Geelen",
  426. author= "Bertrand Guenin",
  427. journal= "Journal of Combinatorial Theory, Series B",
  428. volume= 86,
  429. number= 2,
  430. pages= 280--295,
  431. year= 2002,
  432. publisher= "Elsevier"
  433. }

  434. @article{ibaraki1991wtl,
  435. title= "Weak Three-Linking in Eulerian Digraphs",
  436. author= "Toshihide Ibaraki",
  437. author= "Svatopluk Poljak",
  438. journal= "SIAM journal on Discrete Mathematics",
  439. volume= 4,
  440. pages= 84--98,
  441. year= 1991
  442. }

  443. @article{karp1975ccc,
  444. title= "On the computational complexity of combinatorial problems",
  445. author= "Richard M. Karp",
  446. journal= "Networks",
  447. volume= 5,
  448. number= 1,
  449. pages= 45--68,
  450. year= 1975
  451. }

  452. @article{kramer1984cwr,
  453. title= "The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits",
  454. author= "Mark R. Kramer",
  455. author= "Jan van Leeuwen",
  456. journal= "Advances in computing research",
  457. volume= 2,
  458. pages= 129--146,
  459. year= 1984
  460. }

  461. @article{lomonosov1985cam,
  462. title= "Combinatorial approaches to multiflow problems",
  463. author= "Michael Lomonosov",
  464. journal= "Discrete Applied Mathematics",
  465. volume= 11,
  466. number= 1,
  467. pages= 1--93,
  468. year= 1985
  469. }

  470. @inproceedings{LomonosovSebo93,
  471. author = "Michael Lomonosov",
  472. author = "András Sebő",
  473. title = "On the geodesic-structure of graphs: a polyhedral approach to metric decomposition",
  474. booktitle = "Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization, IPCO'93 (Erice, Sicily, April 29 - May 1, 1993)",
  475. pages = 221--234,
  476. year = 1993,
  477. editor = "Giovanni Rinaldi",
  478. editor = "Lawrence A. Wolsey",
  479. publisher = "CORE, Mathematical Programming Society"
  480. }

  481. @article{lucchesi1978mtd,
  482. title= "A minimax theorem for directed graphs",
  483. author= "Cláudio Leonardo Lucchesi",
  484. author = "Daniel H. Younger",
  485. journal= "J. London Math. Soc",
  486. volume= 17,
  487. number= 2,
  488. pages= 369--374,
  489. year= 1978
  490. }

  491. @article{lynch1975etp,
  492. title= "The equivalence of theorem proving and the interconnection problem",
  493. author= "James F. Lynch",
  494. journal= "ACM SIGDA Newsletter",
  495. volume= 5,
  496. number= 3,
  497. pages= 31--36,
  498. year= 1975,
  499. publisher= "ACM New York, NY, USA"
  500. }

  501. @article{marx2004edp,
  502. title= "Eulerian disjoint paths problem in grid graphs is NP-complete",
  503. author= "Dániel Marx",
  504. journal= "Discrete Applied Mathematics",
  505. volume= 143,
  506. pages= 336--341,
  507. year= 2004,
  508. publisher= "Elsevier"
  509. }

  510. @article{middendorf1993cdp,
  511. title= "On the complexity of the disjoint paths problem",
  512. author= "Matthias Middendorf",
  513. author= "Frank Pfeiffer",
  514. journal= "Combinatorica",
  515. volume= 13,
  516. number= 1,
  517. pages= 97--107,
  518. year= 1993,
  519. publisher= "Springer"
  520. }

  521. @article{muller2006cpd,
  522. title= "On the complexity of the planar directed edge-disjoint paths problem",
  523. author= "Dirk Müller",
  524. journal= "Mathematical Programming",
  525. volume= 105,
  526. number= 2,
  527. pages= 275--288,
  528. year= 2006,
  529. publisher= "Springer"
  530. }

  531. @article{nagamochi1990multicommodity,
  532. title= "Multicommodity flows in certain planar directed networks.",
  533. author= "Hiroshi Nagamochi",
  534. author= "Toshihide Ibaraki",
  535. journal= "Discrete Appl. Math.",
  536. volume= 27,
  537. number= 1,
  538. pages= 125--145,
  539. year= 1990
  540. }

  541. @article{mpa2pairs2010,
  542. author = "Guyslain Naves",
  543. title = "The hardness of routing two pairs on one face",
  544. journal = "Mathematical Programming",
  545. pages = 49--69,
  546. volume = 131,
  547. year = 2012,
  548. publisher = "Springer",
  549. url = "editor" "http://www.springerlink.com/content/50810447h5174596/",
  550. url = "pdf" "af://guyslain/papiers/biflows.pdf",
  551. url = "hal" "http://hal.archives-ouvertes.fr/hal-00313944/fr/"
  552. }

  553. @unpublished{dpathsplanar2010,
  554. author = "Guyslain Naves",
  555. title = "On disjoint paths in acyclic planar graphs",
  556. year = 2010,
  557. note = "Submitted",
  558. url = "pdf" "af://guyslain/papiers/paths_on_dag.pdf",
  559. url = "beamer" "af://guyslain/slides/pres-optimization-days-2011.pdf",
  560. url = "hal" "http://hal.archives-ouvertes.fr/hal-00510749/fr/",
  561. url = "callcc" "af://callcc/Guyslain/Works/acyclic_eulerian_dags"
  562. }

  563. @inbook{multiflowtableau2008,
  564. author = "Guyslain Naves",
  565. author = "András Sebő",
  566. title = "Multiflow Feasibility: an annotated tableau",
  567. booktitle = "Research Trends in Combinatorial Optimization",
  568. editor = "William J. Cook",
  569. editor = "László Lovász",
  570. editor = "Jens Vygen",
  571. pages = 261--283,
  572. publisher = "Springer",
  573. year = 2008,
  574. url = "editor" "http://www.springerlink.com/content/glu12176217w3w36/",
  575. url = "pdf" "af://guyslain/papiers/tableau.pdf",
  576. url = "hal" "http://hal.archives-ouvertes.fr/hal-00313948/fr/"
  577. }


  578. @article{okamura1981mfp,
  579. title= "Multicommodity flows in planar graphs",
  580. author= "Haruko Okamura",
  581. author= "Paul D. Seymour",
  582. journal= "J. Combinat. Theory, Ser. B",
  583. volume= 31,
  584. number= 1,
  585. pages= 75--81,
  586. year= 1981
  587. }

  588. @article{onaga1971fcm,
  589. title= "On feasibility conditions of multicommodity flows in networks",
  590. author= "Kenji Onaga",
  591. author= "O. Kakusho",
  592. journal= "IEEE Transactions on Circuit Theory",
  593. volume= 18,
  594. number= 4,
  595. pages= 425--429,
  596. year= 1971
  597. }

  598. @phdthesis{pfeiffer1990kdw,
  599. title= "Zur Komplexitat des Disjunkte-Wege-Problems",
  600. author= "Frank Pfeiffer",
  601. institution= "Universität Bonn",
  602. year= 1990
  603. }

  604. @article{robertson1995gmx,
  605. title= "Graph minors. XIII. The disjoint paths problem",
  606. author= "Neil Robertson",
  607. author= "Paul D. Seymour",
  608. journal= "Journal of Combinatorial Theory, Series B",
  609. volume= 63,
  610. number= 1,
  611. pages= 65--110,
  612. year= 1995,
  613. publisher= "Elsevier"
  614. }

  615. @article{rothschild1966ftc,
  616. title= "Feasibility of two commodity network flows",
  617. author= "Bruce Rothschild",
  618. author= "Andrew Whinston",
  619. journal= "Operations Research",
  620. pages= 1121--1129,
  621. year= 1966,
  622. publisher= "Operations Research Society of America"
  623. }

  624. @article{schrijver1989kba,
  625. title= "The Klein bottle and multicommodity flows",
  626. author= "Alexander Schrijver",
  627. journal= "Combinatorica",
  628. volume= 9,
  629. number= 4,
  630. pages= 375--384,
  631. year= 1989,
  632. publisher= "Springer"
  633. }

  634. @conference{schrijver1990apc,
  635. title= "Applications of polyhedral combinatorics to multicommodity flows and compact surfaces",
  636. author= "Alexander Schrijver",
  637. booktitle= "Polyhedral Combinatorics: Proceedings of a DIMACS Workshop: June 12-16, 1989",
  638. pages= 119--137,
  639. year= 1990
  640. }

  641. @article{schrijver1990hrm,
  642. title= "Homotopic routing methods",
  643. author= "Alexander Schrijver",
  644. journal= "Paths, Flows, and VLSI-Layout",
  645. pages= 329--371,
  646. year= 1990,
  647. publisher= "Springer Verlag"
  648. }

  649. @conference{schrijver1993cdp,
  650. title= "Complexity of Disjoint Paths Problems in Planar Graphs",
  651. author= "Alexander Schrijver",
  652. booktitle= "Proceedings of the First Annual European Symposium on Algorithms",
  653. pages= 357--359,
  654. year= 1993
  655. }

  656. @article{schrijver1994fkd,
  657. title= "Finding $k$ Disjoint Paths in a Directed Planar Graph",
  658. author= "Alexander Schrijver",
  659. journal= "SIAM Journal on Computing",
  660. volume= 23,
  661. pages= 780--788,
  662. year= 1994
  663. }

  664. @book{schrijver2003cop,
  665. title= "Combinatorial optimization: polyhedra and efficiency",
  666. author= "Alexander Schrijver",
  667. year= 2003,
  668. publisher= "Springer"
  669. }

  670. @book{schrijver1986theory,
  671. title= "Theory of linear and integer programming",
  672. author= "Alexander Schrijver",
  673. year= 1986,
  674. publisher= "Wiley"
  675. }

  676. @article{schwarzler08,
  677. title= "On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary",
  678. author= "Werner Schwärzler",
  679. journal= "Combinatorica",
  680. volume= 29,
  681. number= 1,
  682. pages= 121--126,
  683. year= 2009,
  684. publisher= "Springer"
  685. }

  686. @article{sebHo1993ipm,
  687. title= "Integer plane multiflows with a fixed number of demands",
  688. author= "András Sebő",
  689. journal= "Journal of Combinatorial Theory Series B",
  690. volume= 59,
  691. number= 2,
  692. pages= 163--171,
  693. year= 1993,
  694. publisher= "Academic Press, Inc. Orlando, FL, USA"
  695. }

  696. @article{seymour80a,
  697. author = "Paul D. Seymour",
  698. title = "Decomposition of regular matroids",
  699. journal = "J. Comb. Theory, Ser. B",
  700. volume = 28,
  701. number = 3,
  702. year = 1980,
  703. pages = 305--359
  704. }

  705. @article{seymour1981oca,
  706. title= "On odd cuts and plane multicommodity flows",
  707. author="Paul D. Seymour",
  708. journal= "Proceedings of the London Mathematical Society",
  709. volume= 3,
  710. number= 1,
  711. pages= 178--192,
  712. year= 1981
  713. }

  714. @article{seymour1981mam,
  715. title= "Matroids and multicommodity flows",
  716. author= "Paul D. Seymour",
  717. journal= "European Journal of Combinatorics",
  718. volume= 2,
  719. number= 3,
  720. pages= 257--290,
  721. year= 1981
  722. }

  723. @article{vygen1995ncs,
  724. title= "NP-completeness of some edge-disjoint paths problems",
  725. author= "Jens Vygen",
  726. journal= "Discrete Applied Mathematics",
  727. volume= 61,
  728. number= 1,
  729. pages= 83--90,
  730. year= 1995,
  731. publisher= "Elsevier"
  732. }


  733. @unpublished{vygen98tr,
  734. author = "Jens Vygen",
  735. title = "Disjoint paths, Report No. 94816",
  736. institution = "Institute for Discrete Mathematics, Bonn",
  737. note = "",
  738. year = 1998
  739. }


  740. :}}