{"entities":{"Q1095157":{"pageid":1105909,"ns":120,"title":"Item:Q1095157","lastrevid":69942717,"modified":"2026-04-13T11:22:51Z","type":"item","id":"Q1095157","labels":{"en":{"language":"en","value":"Exact arborescences, matchings and cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4027518"}},"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":"Q1095157$D01A6E40-D3A8-4016-A4E5-62679D86773A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5b9fae387de3fdc40a3f7285cf44fe0c8b300fe","datavalue":{"value":{"text":"Exact arborescences, matchings and cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095157$5DC03593-6D51-4C09-BA5E-22539DD2B3A0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6362facf30e7594508cfde8c09f563acd5753e0","datavalue":{"value":"0632.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095157$5CC61041-3043-4D35-B3F1-13EA52C23D8E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"30267b72669e368a41a6ffbe3e4aed5ed6506d27","datavalue":{"value":"10.1016/0166-218X(87)90067-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095157$B855C581-AEF0-4DD8-AEAB-F72259D7DF2E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$FCFA1858-D938-4825-B077-03F0B1E40C21","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1095157$82B16BA7-EBC0-4961-ABC1-59FE97B5DAD0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef334999ff83d659384cb1a43c9cca3eeac2b1bf","datavalue":{"value":"Given a graph in which each edge has an integral weight, an exact problem is to determine whether a desired structure exists for which the sum of the edge weights is exactly k for some specified k. Given a directed graph with a specified vertex r, an arborescence rooted at r is a set of arcs which induce a connected directed subgraph such that r has indegree zero and all other vertices have indegree one. The existence of polynomial algorithms is shown for exact arborescence, exact spanning tree, exact perfect matching in planar graphs, and exact cycle sum for a class of planar directed graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$607E5E74-1B59-4945-91BB-3364E5970AFF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095157$9CAE429B-6BAC-4D2E-B03E-42204D1C2B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095157$9915EEF1-91CE-4FAA-88FF-C32851C3EBB6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5ea26abfd9eb846e9aeb0caad22cbd8c1322545","datavalue":{"value":"4027518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095157$DCB8B6B5-35FF-4BE3-B801-F6567F86F942","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$7777BC5A-B63A-42A6-BD39-FC14D85F8D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"150b809fd0be0d31c43b2e18ef8f76a7cef79188","datavalue":{"value":"arborescence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$C873BBC1-1995-4221-A4CE-B3D62E2BF36C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$454B172B-AF9B-4332-B71E-8BB838F3BE95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cb6e674c4215c18197af07a351a4901f2737056","datavalue":{"value":"exact spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$8DA419B1-25D7-4CF1-9A64-8880A356E8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b05e09ff6c4cfe848028f06a18074430b726b786","datavalue":{"value":"exact perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$18D610EE-171E-4841-A8E2-C8A5584C7042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$CFF77BFC-130D-49A6-BCA3-08978EFA4B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa01ae40c7b2bf18762a4873586be73af4e7f5ca","datavalue":{"value":"exact cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$14E36D05-164C-4B37-BA00-16656C973AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f52dd19283d0a086cca1b0dd1533b225238396b","datavalue":{"value":"planar directed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095157$745555F5-DD34-4255-9BCA-BE037550C471","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65634c2d7f7dfc4f36bec0cd396792e04d171618","datavalue":{"value":{"entity-type":"item","numeric-id":270026,"id":"Q270026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$2328CDB9-7F4F-4A8C-AD8F-8278D7B4BC93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff87f54c8625b230f23e0ff9df421fd57253f22c","datavalue":{"value":{"entity-type":"item","numeric-id":582214,"id":"Q582214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$BE9F93FF-7582-4FE6-A546-983A175FED8F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d3b25dc30b75558579c988a512f98264c780de85","datavalue":{"value":{"entity-type":"item","numeric-id":1171577,"id":"Q1171577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$181B52B9-B013-4795-9569-B5A138B50DB5","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":"Q1095157$EF039F78-7F01-49B5-8150-B04B3F9B6A81","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"949f17675a405c19c00b011a36c2e4bf6a9d3dcb","datavalue":{"value":{"entity-type":"item","numeric-id":5645231,"id":"Q5645231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$1311B6E3-9A43-4D5F-9DB9-9E2EA9AB7D4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70c9ac7377038fbff666889faaa51e36daf21586","datavalue":{"value":{"entity-type":"item","numeric-id":1245845,"id":"Q1245845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$19C22153-DB84-42B0-A3F4-7C555E7A0708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0479e2411231996c037adbcede0345cb47efc22","datavalue":{"value":{"entity-type":"item","numeric-id":5567717,"id":"Q5567717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$3AA6A09F-DE7F-4AE3-AEB7-35B39889609D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ab456935031c732c9df7e77ae45d7cb3ea982cb","datavalue":{"value":{"entity-type":"item","numeric-id":5537097,"id":"Q5537097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$C0E4C5A3-9555-4C56-967A-2786C6ABACA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$0B8A1FDE-8E09-4486-B858-BF62696DFA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cad6d6356fb2aabced35b1a059812873a319983d","datavalue":{"value":{"entity-type":"item","numeric-id":4769069,"id":"Q4769069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$FB6D9561-F6CE-4CB9-882E-74EE6F57871C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c45c86c7f172e023843236094a98399ae49d365","datavalue":{"value":{"entity-type":"item","numeric-id":4165177,"id":"Q4165177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$50586250-55E0-40EF-86A4-6787C6DF8291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9beef10f14c1534c9b646b394bb6806fa6bcf5a6","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$DE73B4E4-38CC-4572-96DD-7648125EF42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95ac60093948df00a6d95c2fbc5d8b2ff34bd5d6","datavalue":{"value":{"entity-type":"item","numeric-id":4178800,"id":"Q4178800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$20DB8394-7BB0-42B5-A7F8-438407BFFC40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbdd4cf597b5efaf84d98e3a02b2ec5b678a450","datavalue":{"value":{"entity-type":"item","numeric-id":5605168,"id":"Q5605168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$5CABD7CA-1015-49B1-A874-1D1A2BB4CA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4324d74dffdd686a688ce05fefc1066bdbeda16a","datavalue":{"value":{"entity-type":"item","numeric-id":3936213,"id":"Q3936213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095157$9E9A233B-623E-4073-8C67-7EA7346AD04B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ff31b9316e654cbbbc855661b6d344748ec836e","datavalue":{"value":{"entity-type":"item","numeric-id":3827810,"id":"Q3827810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"567758ef25ef655466995a4f82f7333850b35f46","datavalue":{"value":{"amount":"+0.7833571434020996","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":"Q1095157$2AFE3817-2986-4FE3-B10D-5EE947E2B6C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a7c5c8ac3ca44eb0c294a7b575f6e35800cfd7d","datavalue":{"value":{"entity-type":"item","numeric-id":3990608,"id":"Q3990608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c2d9dae86ba8c95e90c62a9cb8d415dcff3af8c","datavalue":{"value":{"amount":"+0.7809515595436096","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":"Q1095157$C46E92F2-720E-40C6-BA48-E3CB6AD13BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73383379772714e0d12158739d75eeaa94d041cb","datavalue":{"value":{"entity-type":"item","numeric-id":6155599,"id":"Q6155599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c86265c70ce52d95b4b7a22ab0cf9d11c9e04f79","datavalue":{"value":{"amount":"+0.7808642983436584","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":"Q1095157$0329B21A-A60F-490E-8D9A-7F30A5B3B8A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5973d038daf45c5b9e70ef634e2c1fe968dac296","datavalue":{"value":{"entity-type":"item","numeric-id":3603472,"id":"Q3603472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eaf56d7850603834ee6ecf1e89d956b2d19a9c2","datavalue":{"value":{"amount":"+0.7704148292541504","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":"Q1095157$0FFF03B9-49BC-4874-B61B-AC2A0939B304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea9d7c720fc2f0364134f8d5cb79ff96c52b3253","datavalue":{"value":{"entity-type":"item","numeric-id":2429356,"id":"Q2429356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7cb0d0e9a9f38fb1482583ea22efe37bf7a98a4","datavalue":{"value":{"amount":"+0.7700223922729492","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":"Q1095157$4FF913A9-AB80-498E-A32A-63B781159001","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exact arborescences, matchings and cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Exact_arborescences,_matchings_and_cycles"}}}}}