{"entities":{"Q1126868":{"pageid":1137617,"ns":120,"title":"Item:Q1126868","lastrevid":66188562,"modified":"2026-04-12T08:08:31Z","type":"item","id":"Q1126868","labels":{"en":{"language":"en","value":"Routing and timetabling by topological search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1184405"}},"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":"Q1126868$BB1C555C-F854-48E1-AE2E-E5D649D36867","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"473a1f6f24966dfd25e3a0c287e0b5dc4a9afcd0","datavalue":{"value":{"text":"Routing and timetabling by topological search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1126868$46924044-D7EB-4B28-BC57-CF03B571B70E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e560ceb7b8c1c37e79a510b4926abaa826fff28","datavalue":{"value":"0901.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$B04CE3E2-62C9-4648-A85A-52BE73FFEB6D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4add3c5163a5eee9bbe20dc8a36386ab43b68fd6","datavalue":{"value":{"entity-type":"item","numeric-id":168490,"id":"Q168490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126868$C038FFDF-9448-41B0-9DB2-760509A6AB52","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3db2eb2e003c0308e77b1da3e621f97dd9657c54","datavalue":{"value":{"time":"+1998-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1126868$702D56D8-EB82-4B32-8ACC-671655CC05F5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8890a1667853c9df863345ac5dc598630521680d","datavalue":{"value":"https://eudml.org/doc/233084","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126868$90B03949-B544-4035-9850-FC7F565A7144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f011cfe00c5ccdb2b6a9bec97325f2b88781cec","datavalue":{"value":"http://www.emis.de/journals/DMJDMV/xvol-icm/17/Schrijver.MAN.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126868$FD50B779-1F3A-4EB7-970A-9D7219BD5442","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"30a325f971e11f94ea28a4a85b6df0a6af67b6b6","datavalue":{"value":"This is a survey paper. The author shows how decomposing the search space into homotopy classes can help in finding solutions to combinatorial optimization problems. The method is illustrated on two specific classes of NP-complete problems: the \\(k\\) disjoint paths problem for directed planar graphs when \\(k\\) is fixed, and the problem of finding a periodic timetable (applied to the Dutch railway timetable).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$E8CBC407-D692-4B92-BFF1-5CC3C83C4E56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$69CE46F3-85D8-4782-9D42-83F13AE1410F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$A07212AA-29D6-4E5E-B043-CC8FD600C9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"810d660658648f9bc3138c1cd0aba8029bb9050c","datavalue":{"value":"90B06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$C9201BDF-B5E0-409A-9BF9-5221ED4B00AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$E570FC40-74B1-444D-BCA7-6EB432114BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$4EF3B9C6-15D3-4575-B33B-152AE2211B2D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8413972081c53f6a2fa5709711f724de90ff8a21","datavalue":{"value":"1184405","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$EB1D669D-FC06-4E70-BA82-AEA12ACBB5AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23b3bde190595f1a442cc36db70193632c0e99b1","datavalue":{"value":"homotopy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$D3BAE3A3-024D-4053-80D9-6FB8D9A233D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8415b13e13866b2a902e773eb49890a053b3a53","datavalue":{"value":"disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$A9B59947-472E-40C9-8F36-9C9078AD29AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be9847b5080561732e2df3fe2a5afade2166808c","datavalue":{"value":"routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$03407790-AAE7-46FB-9CE5-8E868003BE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25fa47f9463d515b352593e567b1400b4df9f27b","datavalue":{"value":"timetabling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$FF978107-40B5-4E9F-B545-82AB844AA38D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1415b5076f67632c691653a2c3dd9ad41514b720","datavalue":{"value":"closed curves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$E46B91FC-6E72-461C-B528-23759088393A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"577c070866bfc3759b53cf2111a310601b48b9df","datavalue":{"value":"compact surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$2E71BF30-6751-4594-8312-75A17A77D672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421a43f4b0e8832a026eaa34353c95869f115bee","datavalue":{"value":"survey","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$F968DDF6-56AD-4E7E-8564-1C684529B7F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73e1fdc457ecf54ed3bcf9b3400c96ffa8edd4c0","datavalue":{"value":"search space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$8693B159-67D9-4C4C-9ABF-7ECB06A5AE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38158c9a510219d0c8167770b4313ea49dee4b8b","datavalue":{"value":"homotopy classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$C4A0A9B7-EC0E-4B32-9BF4-C63ADDB71F94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$12098F42-02AA-46B8-ACA7-BB45583E3ECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$13387662-7AB6-4D27-B330-BCD82B855F64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$F34FB3CB-4017-4225-8C06-A790C0E3A834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc92fcc6eec96952be2de3c0106ad36885fc8473","datavalue":{"value":"periodic timetable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126868$7DF827D1-1EF3-4521-97D6-E402A7DC1BE4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4fefa17be9d4bfc1a51cd1d93e86e23724d8c0a1","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126868$B968CA02-5E1D-45A8-8CE3-8B6FA931CAE2","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":"Q1126868$50E9EBFC-705B-4858-AFEF-88032614C851","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"35266596044914f2a67d99bd7a5143302ec6df27","datavalue":{"value":"bafkreiek4canbd223dohre6qkcqlqob275riulxaivhmh6l5c4awhnswra","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126868$94D83607-9253-4BD3-85AE-A69BB08C175B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dbf8d5cbd9ece6bead4e0fa5d545881c7f63f46","datavalue":{"value":{"entity-type":"item","numeric-id":6481473,"id":"Q6481473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126868$9024C860-E7E8-46A9-B551-F62AA3AF72CB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cdd0874e7e90971cbb9e5fa1a04833034a21a6d","datavalue":{"value":{"entity-type":"item","numeric-id":3360021,"id":"Q3360021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49fe14550301427198c30ee4d5494de37a0f8a57","datavalue":{"value":{"amount":"+0.7378208637237549","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":"Q1126868$4B3B61FF-E2BD-4D77-ADFC-B9AB23EDA5A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9387ff795cb59f85cc8d17c6aa2081cf8a36333c","datavalue":{"value":{"entity-type":"item","numeric-id":1923597,"id":"Q1923597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0590d4c6e0802a6144627f33b11668e6262d55dd","datavalue":{"value":{"amount":"+0.7375614047050476","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":"Q1126868$22B34F4F-BDC9-43AC-A850-0BD1FDA4324C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da00eb947c337687941dd1e5792ffa1e3574ec84","datavalue":{"value":{"entity-type":"item","numeric-id":3813339,"id":"Q3813339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30047c3bbd26bf06e5ca6c1b4dfcf6b1fa81c419","datavalue":{"value":{"amount":"+0.732994019985199","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":"Q1126868$8A56BDA5-1C2D-4BB3-9856-863616DBA3B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2ae936f0589ea04a8b67ca0740a4e28fcdf3b90","datavalue":{"value":{"entity-type":"item","numeric-id":1407255,"id":"Q1407255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e118e24ef09b2bde78bcdc7d49db3690cc79188f","datavalue":{"value":{"amount":"+0.706062376499176","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":"Q1126868$45FBA1E7-B885-4711-BFDD-A17CAE412FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24e00e28a5fcde82cce83a47d99cacaf5231dfe1","datavalue":{"value":{"entity-type":"item","numeric-id":4291553,"id":"Q4291553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a295dbc341e48cadcf395f11ad4ceb1d386b4b6","datavalue":{"value":{"amount":"+0.7054179906845093","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":"Q1126868$36333437-FD69-4380-BFBC-15AB7C017B3D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Routing and timetabling by topological search","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Routing_and_timetabling_by_topological_search"}}}}}