{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:04Z","timestamp":1759637944746},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_68","type":"book-chapter","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T21:40:34Z","timestamp":1441057234000},"page":"816-827","source":"Crossref","is-referenced-by-count":4,"title":["On the Pathwidth of Almost Semicomplete Digraphs"],"prefix":"10.1007","author":[{"given":"Kenta","family":"Kitsunai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisao","family":"Tamaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"68_CR1","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: theory, algorithms and applications. Springer Science & Business Media (2008)","DOI":"10.1007\/978-1-84800-998-1"},{"key":"68_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"68_CR3","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.aim.2014.11.011","volume":"270","author":"M. Chudnovsky","year":"2015","unstructured":"Chudnovsky, M., Scot, A., Seymour, P.: Disjoint paths in tournaments. Advances in Mathematics\u00a0270, 582\u2013597 (2015)","journal-title":"Advances in Mathematics"},{"issue":"1","key":"68_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2010.10.003","volume":"101","author":"M. Chudnovsky","year":"2011","unstructured":"Chudnovsky, M., Seymour, P.: A well-quasi-order for tournaments. Journal of Combinatorial Theory, Series B\u00a0101(1), 47\u201353 (2011)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"68_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science\u00a010(2), 111\u2013121 (1980)","journal-title":"Theoretical Computer Science"},{"key":"68_CR6","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Pilipczuk, M.: Jungles, bundles, and fixed-parameter tractability. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 396\u2013413 (2013)","DOI":"10.1137\/1.9781611973105.29"},{"issue":"3","key":"68_CR7","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.jctb.2013.03.001","volume":"103","author":"A.O. Fradkin","year":"2013","unstructured":"Fradkin, A.O., Seymour, P.D.: Tournament pathwidth and topological containment. Journal of Combinatorial Theory, Series B\u00a0103(3), 374\u2013384 (2013)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"68_CR8","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jctb.2014.07.002","volume":"110","author":"A. Fradkin","year":"2015","unstructured":"Fradkin, A., Seymour, P.: Edge-disjoint paths in digraphs with bounded independence number. Journal of Combinatorial Theory, Series B\u00a0110, 19\u201346 (2015)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"68_CR9","unstructured":"Kistunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Computing directed pathwidth in O(1.89n) time. Algorithmica (2015) (accepted for publication)"},{"key":"68_CR10","doi-asserted-by":"crossref","unstructured":"Kistunai, K., Kobayashi, Y., Tamaki, H.: On the pathwidth of almost semicomplete digraphs. arXiv preprint arXiv:1507.01934 (2015)","DOI":"10.1007\/978-3-662-48350-3_68"},{"key":"68_CR11","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.jctb.2014.12.005","volume":"112","author":"I. Kim","year":"2015","unstructured":"Kim, I., Seymour, P.: Tournament minors. Journal of Combinatorial Theory, Series B\u00a0112, 138\u2013153 (2015)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"68_CR12","doi-asserted-by":"crossref","unstructured":"Nagamochi, H.: Linear layouts in submodular systems. In: Proceedings of the 23rd International Symposium on Algorithms and Computation, pp. 475\u2013484 (2012)","DOI":"10.1007\/978-3-642-35261-4_50"},{"key":"68_CR13","unstructured":"Pilipczuk, M.: Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. arXiv preprint arXiv:1210.5363 (2012) Conference version in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, pp. 197\u2013208 (2013)"},{"issue":"1","key":"68_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B\u00a063(1), 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"68_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. Journal of Combinatorial Theory, Series B\u00a092(2), 325\u2013357 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"68_CR16","doi-asserted-by":"crossref","unstructured":"Tamaki, H.: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, pp. 331\u2013342 (2011)","DOI":"10.1007\/978-3-642-25870-1_30"},{"issue":"10","key":"68_CR17","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.dam.2007.08.045","volume":"156","author":"B. Yang","year":"2008","unstructured":"Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discrete Applied Mathematics\u00a0156(10), 1822\u20131837 (2008)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_68","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T16:12:28Z","timestamp":1559232748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}