{"entities":{"Q876503":{"pageid":878351,"ns":120,"title":"Item:Q876503","lastrevid":65046681,"modified":"2026-04-11T23:57:47Z","type":"item","id":"Q876503","labels":{"en":{"language":"en","value":"Complexity of the minimum-length corridor problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5144505"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$6E18A1CC-638C-490D-8F66-A7A1BA24D16D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b84f50dc24bf161577502841ae7a247ee86fe2f4","datavalue":{"value":{"text":"Complexity of the minimum-length corridor problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q876503$D921B24D-B43D-456B-80C2-F53F807E4F2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0e07578df31a40bf0fa80f03c039e6b166cb2232","datavalue":{"value":"1117.65035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$EAB4C7C7-06A2-4405-8947-78BD06A36B31","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7fd166189e30417898671ab89b2b1f585e5b7d93","datavalue":{"value":{"entity-type":"item","numeric-id":876502,"id":"Q876502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$3D17EFA5-55AB-45CA-9F20-50F65BB8DFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc11152e79285b1105c94eee7fb922884a1cabd0","datavalue":{"value":{"entity-type":"item","numeric-id":293372,"id":"Q293372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$34301339-14EB-4EB2-BFBE-E0989B4B252B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$692D363D-54B1-4237-A0C5-F9F134BB92B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6f339c49c589764265da0f7de34a17b3e7a78e06","datavalue":{"value":{"time":"+2007-04-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q876503$4D408940-5402-4EA6-957B-2D0A8571AFC4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1a46f3fa42c61b7c299bb938913a5909e6bdf2b","datavalue":{"value":"The authors study the minimum-length corridor (MLC) problem and some of its variants. More precisely, given a rectangular boundary partitioned into rectilinear polygons, the problem consists in finding a corridor of least total length. A corridor is a set of line segments each of which must lie along the line segments that form the rectangular boundary and/or the boundary of the rectilinear polygons. The corridor is a tree, and must include at least one point from the rectangular boundary and at least one point from the boundary of each of the rectilinear polygons. In this paper, it is established that the MLC problem is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q876503$E5D8871F-D513-4CDD-9AC1-0456D4B78C54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$868AE9FA-453A-4ECD-A09D-914FFD66DFAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$5B5D44F4-8532-4057-A0BC-FD25358CABBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$F29A8422-23A4-40DB-9427-A4F4B332F57D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c2b40389ae16c00c4f112848c4664733e181470","datavalue":{"value":"5144505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$DA9C5501-ACEF-4952-B36A-2A49192C92A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q876503$F85A6B2E-7441-4D02-991A-07D3F26BBE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0067ee569a3db070fdfe86278dd54813d48d5336","datavalue":{"value":"minimum optical fiber length","type":"string"},"datatype":"string"},"type":"statement","id":"Q876503$3A1161A3-47BF-4AB0-A89C-6FAFEB35878E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eabcaa4115c7d203cf999b1d6476a35edc125dbe","datavalue":{"value":{"entity-type":"item","numeric-id":256764,"id":"Q256764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$72B2DBA7-9247-4791-868F-C4D03D7BB69F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$E30AA420-0A62-4D2A-9B0C-D7E49B2882DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef5c48c1cd1419c41f04196fec97b9e4998eaf54","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2006.10.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q876503$9777E79A-DC5D-401E-AF79-144CE9853CB1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0a8f244d215529b330250d7eafc33e277d95b0b","datavalue":{"value":"W2038002703","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$A3EC7AD3-EB08-41F7-8BA9-10AEFDEEA55D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c28227e02cb5aa673d236d230a232082fd8c5212","datavalue":{"value":{"entity-type":"item","numeric-id":688437,"id":"Q688437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$65F80B44-6C81-46D6-B4B1-3AF0E7054F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d63a3ff9613eac0f7f99ed7f1892afa8b907204","datavalue":{"value":{"entity-type":"item","numeric-id":2709886,"id":"Q2709886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$498AF360-019A-4A8B-9218-95E0FC0CCBB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e25938889e3901950168d449f509b68340f58426","datavalue":{"value":{"entity-type":"item","numeric-id":4028109,"id":"Q4028109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$E9BB108E-F2DA-4E55-9955-FDA9FF9DDA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$C3D59CF3-15B4-4FB9-A70C-6DF168A5129C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$5CECD6A6-A430-4784-886D-F3B07E67E084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ba287703bcdfe2f73ef8b56b1010aaf445322c3","datavalue":{"value":{"entity-type":"item","numeric-id":4694752,"id":"Q4694752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$8884AF85-61A7-4BAD-8734-B72FE4D7739C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67780914d87571b65714f2935ed525d34a20a0bd","datavalue":{"value":{"entity-type":"item","numeric-id":5897267,"id":"Q5897267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876503$38692F77-32BC-4FD4-BCB1-458A51D52CE1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5eab618ca1a8671d400f91b770163751b2442a83","datavalue":{"value":"10.1016/J.COMGEO.2006.10.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876503$52215D2F-EE99-4150-A1BB-740B7E72F970","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0b543c5d6aece047f241a831e861a5573bf780a","datavalue":{"value":{"entity-type":"item","numeric-id":5443510,"id":"Q5443510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdad1b24f1a3d0ee9fdaba312d2cbcd7c61a7390","datavalue":{"value":{"amount":"+0.8197030425071716","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876503$A283A6D6-8547-432C-9ED4-3335D558029A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c694050ade6a5241974b5543b5bf936487a784c0","datavalue":{"value":{"entity-type":"item","numeric-id":2930339,"id":"Q2930339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f2a8d82f509e53488a80724f34197bdb41cd1f2","datavalue":{"value":{"amount":"+0.8186149597167969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876503$015988C1-C51F-48C2-AD31-AC01EB9AC240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4c9dc2af4c079994458b9ab55327a3975ce8ebc","datavalue":{"value":{"entity-type":"item","numeric-id":833722,"id":"Q833722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3da7f4384e38818a9657587820c9484af97cc2b","datavalue":{"value":{"amount":"+0.8164244890213013","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876503$BB375CD0-2F03-40AF-B93B-E556C2FDB772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a26253254c18476fdc37a0a01561ca1d4b5d5862","datavalue":{"value":{"entity-type":"item","numeric-id":456091,"id":"Q456091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fcc4a530b5f2d816a37d9fb36551ef42c2d4124","datavalue":{"value":{"amount":"+0.8052696585655212","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876503$949EB8D5-7C89-4B6B-9F52-AF48E9016A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34c8666803e542b72cf1d072453ea3cad146615c","datavalue":{"value":{"entity-type":"item","numeric-id":582084,"id":"Q582084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b1bdff2f3930bf2fbe3622a13f8e86853006a2d","datavalue":{"value":{"amount":"+0.7304764986038208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q876503$BFF508A6-C2AB-4006-A3C7-90C7470D80FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of the minimum-length corridor problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_the_minimum-length_corridor_problem"}}}}}