{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T14:54:13Z","timestamp":1770476053329,"version":"3.49.0"},"reference-count":25,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1998,7,1]],"date-time":"1998-07-01T00:00:00Z","timestamp":899251200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1998,7,1]],"date-time":"1998-07-01T00:00:00Z","timestamp":899251200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[1998,9,8]],"date-time":"1998-09-08T00:00:00Z","timestamp":905212800000},"content-version":"vor","delay-in-days":69,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1998,7]]},"DOI":"10.1016\/s0166-218x(98)00036-5","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T19:10:20Z","timestamp":1052766620000},"page":"203-222","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":19,"title":["The planar multiterminal cut problem"],"prefix":"10.1016","volume":"85","author":[{"given":"David","family":"Hartvigsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(98)00036-5_BIB1","series-title":"Advanced Techniques in the Practice of Operations Research","first-page":"333","article-title":"Matroids and operations research","author":"Bixby","year":"1982"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/net.3230210106","article-title":"On the multiway cut polyhedron","volume":"21","author":"Chopra","year":"1991","journal-title":"Networks"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB3","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1090\/dimacs\/005\/07","article-title":"The optimal multiterminal cut problem","volume":"vol. 5","author":"Cunningham","year":"1991","journal-title":"D1MACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB4","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","article-title":"The complexity of multiway cuts","volume":"23","author":"Dahlhaus","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB5","series-title":"The minimum 3-cut problem: an application of polyhedral combinatorics, honors project","author":"Fiala","year":"1986"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB6","series-title":"Flows in Networks","author":"Ford","year":"1962"},{"issue":"6","key":"10.1016\/S0166-218X(98)00036-5_BIB7","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","article-title":"Fast algorithms for shortest paths in planar graphs, with applications","volume":"16","author":"Frederickson","year":"1987","journal-title":"SIAM. J. Comput."},{"issue":"1","key":"10.1016\/S0166-218X(98)00036-5_BIB8","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","article-title":"A polynomial algorithm for the k-cut problem for fixed k","volume":"19","author":"Goldschmidt","year":"1994","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB9","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","article-title":"Multi-terminal network flows","volume":"9","author":"Gomory","year":"1961","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1006\/jagm.1993.1033","article-title":"Minimum path bases","volume":"15","author":"Hartvigsen","year":"1993","journal-title":"J. Algorithms"},{"issue":"3","key":"10.1016\/S0166-218X(98)00036-5_BIB11","doi-asserted-by":"crossref","DOI":"10.1137\/S0895480190177042","article-title":"The all-pairs min cut problem and the min cycle basis problem on planar graphs","volume":"7","author":"Hartvigsen","year":"1994","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0167-6377(95)00018-F","article-title":"Multiterminal flows and cuts","volume":"17","author":"Hartvigsen","year":"1995","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"10.1016\/S0166-218X(98)00036-5_BIB13","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1287\/moor.13.4.535","article-title":"Solution bases of multiterminal cut problems","volume":"13","author":"Hassin","year":"1988","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0196-6774(91)90021-P","article-title":"An improved algorithm for the planar 3-cut problem","volume":"12","author":"He","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB15","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1137\/0606068","article-title":"An O (|V|2) algorithm for the planar 3-cut problem","volume":"6","author":"Hochbaum","year":"1985","journal-title":"SIAM J. Algebraic Discrete Meth."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB16","series-title":"Integer Programming and Network Flows","author":"Hu","year":"1969"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB17","series-title":"Proc. of 26th Annual ACM Symp. on Theory of Computing","first-page":"27","article-title":"Faster shortest-path algorithms for planar graphs","author":"Klein","year":"1994"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB18","first-page":"48","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"7","author":"Kruskal","year":"1956"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB19","series-title":"Matching Theory","author":"Lovasz","year":"1986"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB20","first-page":"340","article-title":"A structural characterization of planar combinatorial graphs","volume":"3","author":"MacLane","year":"1937","journal-title":"Duke Math. J."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB21","first-page":"394","article-title":"Selected applications of minimum cuts in networks","volume":"20","author":"Picard","year":"1982","journal-title":"INFOR"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB22","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell System Technol. J."},{"issue":"1","key":"10.1016\/S0166-218X(98)00036-5_BIB23","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1137\/0212005","article-title":"Minimum s-t cut of a planar undirected network in O(nlog2n) time","volume":"12","author":"Reif","year":"1983","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(98)00036-5_BIB24","series-title":"Data Structures and Network Algorithms","author":"Tarjan","year":"1983"},{"key":"10.1016\/S0166-218X(98)00036-5_BIB25","series-title":"Matroid Theory","author":"Welsh","year":"1976"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X98000365?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X98000365?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T11:56:33Z","timestamp":1759060593000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X98000365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,7]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,7]]}},"alternative-id":["S0166218X98000365"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(98)00036-5","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1998,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"The planar multiterminal cut problem","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0166-218X(98)00036-5","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1998 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}