{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:43:15Z","timestamp":1725482595736},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540673064"},{"type":"electronic","value":"9783540464150"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/10719839_32","type":"book-chapter","created":{"date-parts":[[2007,4,11]],"date-time":"2007-04-11T08:13:55Z","timestamp":1176279235000},"page":"308-317","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract"],"prefix":"10.1007","author":[{"given":"D.","family":"Barth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Corteel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Denise","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Gardy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Valencia-Pabon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,4,12]]},"reference":[{"key":"32_CR1","unstructured":"Aumann, Y., Rabani, Y.: Improved bounds for all optical routing. In: Proc. of the 6th ACM-SIAM SODA, pp. 567\u2013576 (1995)"},{"issue":"4","key":"32_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1006\/eujc.1993.1031","volume":"14","author":"P.. Biane","year":"1993","unstructured":"Biane, P.: Permutations suivant le type d\u2019exc\u00e9dance et le nombre d\u2019inversions et interpr\u00e9tation combinatoire d\u2019une fraction continue de Heine. Eur. J. Comb.\u00a014(4), 277\u2013284 (1993)","journal-title":"Eur. J. Comb."},{"key":"32_CR3","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P.: Wavelength Routing of Symmetric Communication Requests in Directed Fiber Trees. In: Proc. of SIROCCO (1998)"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Cheung, N.K., Nosu, K., Winzer, G. (eds.): Special Issue on Dense Wavelength Division Multiplexing Techniques for High Capacity and Multiple Access Communications Systems. IEEE J. on Selected Areas in Comm. 8(6) (1990)","DOI":"10.1109\/49.57828"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.2307\/1427054","volume":"17","author":"H.E. Daniels","year":"1985","unstructured":"Daniels, H.E., Skyrme, T.H.R.: The maximum of a random walk whose mean path has a maximum. Adv. Appl. Probab.\u00a017, 85\u201399 (1985)","journal-title":"Adv. Appl. Probab."},{"key":"32_CR6","first-page":"221","volume-title":"Proc. of HICSS-30","author":"T. Erlebach","year":"1997","unstructured":"Erlebach, T., Jansen, K.: Call scheduling in trees, rings and meshes. In: Proc. of HICSS-30, vol.\u00a01, pp. 221\u2013222. IEEE CS Press, Los Alamitos (1997)"},{"issue":"1-2","key":"32_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0304-3975(99)00029-8","volume":"221","author":"T. Erlebach","year":"1999","unstructured":"Erlebach, T., Jansen, K., Kaklamanis, C., Mihail, M., Persiano, P.: Optimal wavelength routing on directed fiber trees. Theoret. Comput. Sci.\u00a0221(1-2), 119\u2013137 (1999)","journal-title":"Theoret. Comput. Sci."},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0012-365X(80)90050-3","volume":"32","author":"P.. Flajolet","year":"1980","unstructured":"Flajolet, P.: Combinatorial aspects of continued fractions. Discrete Math.\u00a032, 125\u2013161 (1980)","journal-title":"Discrete Math."},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0012-365X(79)90182-1","volume":"28","author":"J. Fran\u00e7on","year":"1979","unstructured":"Fran\u00e7on, J., Viennot, X.: Permutations selon leurs pics, creux, doubles mont\u00e9es et doubles descentes, nombres d\u2019Euler et nombres de Genocchi. Discrete Math.\u00a028, 21\u201335 (1979)","journal-title":"Discrete Math."},{"issue":"2","key":"32_CR10","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of colouring circular arcs and chords. SIAM J. Alg. Disc. Meth.\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/3-540-63165-8_206","volume-title":"Automata, Languages and Programming","author":"L. Gargano","year":"1997","unstructured":"Gargano, L., Hell, P., Perennes, S.: Coloring all directed paths in a symmetric tree with applications to WDM routing. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 505\u2013515. Springer, Heidelberg (1997)"},{"key":"32_CR12","volume-title":"Algorithmic graph theory and perfect graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press, New York (1980)"},{"key":"32_CR13","volume-title":"Proc. of 10th IPPS","author":"Q.-P. Gu","year":"1996","unstructured":"Gu, Q.-P., Tamaki, H.: Routing a permutation in the Hypercube by two sets of edgedisjoint paths. In: Proc. of 10th IPPS. IEEE CS Press, Los Alamitos (1996)"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks\u00a012, 459\u2013467 (1982)","journal-title":"Networks"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0020-0190(97)00077-X","volume":"62","author":"S.R. Kumar","year":"1997","unstructured":"Kumar, S.R., Panigrahy, R., Russel, A., Sundaram, R.: A note on optical routing on trees. Inf. Process. Lett.\u00a062, 295\u2013300 (1997)","journal-title":"Inf. Process. Lett."},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(87)90028-4","volume":"53","author":"G. Louchard","year":"1987","unstructured":"Louchard, G.: Random walks, Gaussian processes and list structures. Theoret. Comput. Sci.\u00a053, 99\u2013124 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"32_CR17","unstructured":"Paterson, M., Schr\u00f6der, H., S\u00fdkora, O., Vrto, I.: On Permutation Communications in All-Optical Rings. In: Proc. of SIROCCO (1998)"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Upfal, U.: Efficient routing in all optical networks. In: Proc. of the 26th ACM STOC, pp. 133\u2013143 (1994)","DOI":"10.1145\/195058.195119"},{"issue":"3","key":"32_CR19","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A. Tucker","year":"1975","unstructured":"Tucker, A.: Coloring a family of circular arcs. SIAM J. Appl. Maths.\u00a029(3), 493\u2013502 (1975)","journal-title":"SIAM J. Appl. Maths."},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BFb0076539","volume":"1171","author":"X. Viennot","year":"1985","unstructured":"Viennot, X.: A combinatorial theory for general orthogonal polynomials with extensions and applications. Lect. Notes Math.\u00a01171, 139\u2013157 (1985); Polyn\u00f4mes orthogonaux et applications, Proc. Laguerre Symp., Bar-le-Duc\/France (1984)","journal-title":"Lect. Notes Math."},{"key":"32_CR21","unstructured":"Viennot, X.: Une th\u00e9orie combinatoire des polyn\u00f4mes orthogonaux g\u00e9n\u00e9raux. Notes de conf\u00e9rences, Univ. Quebec, Montr\u00e9al (1985)"},{"key":"32_CR22","unstructured":"Wilfong, G., Winkler, P.: Ring routing and wavelength translation. In: Proc. of the 9th Annual ACM-SIAM SODA, pp. 333\u2013341 (1998)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2000: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10719839_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T07:41:08Z","timestamp":1567237268000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10719839_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540673064","9783540464150"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/10719839_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"12 April 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}