{"entities":{"Q911485":{"pageid":913333,"ns":120,"title":"Item:Q911485","lastrevid":65314131,"modified":"2026-04-12T01:44:23Z","type":"item","id":"Q911485","labels":{"en":{"language":"en","value":"On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4141828"}},"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":"Q911485$262B1431-6D3E-464E-BB2B-FB837BBD9B1E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab30762b394d7c78aa5c22ffda75fcbafb09369b","datavalue":{"value":{"text":"On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q911485$4CB09012-8AC4-4041-9953-B647440DAD8F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3348e044448b709c7d881177348e168c8a73633c","datavalue":{"value":"0696.90079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$D97AB413-6A7E-4A47-8873-473AA8F92708","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d1a96f8bcf77f7d0ea078fe0589a61d465d39b8","datavalue":{"value":"10.1016/0167-6377(87)90055-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$7C99A9DE-9D87-4E04-8711-72853648B3CC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$7C4037F4-0786-43C5-9E4E-E966CABCAC29","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$8FF31E23-6A68-4FB2-A7D4-A9C42F6D0FC4","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":"Q911485$8243DB6A-8B45-4C27-912A-33F9646BEC65","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f656402e99cfb94e7df8a8e2c9e00fd72b24dbb5","datavalue":{"value":"A subgraph F of a graph \\(G=(V,E)\\) is called a perfectly matchable subgraph (PMS) if F contains a set of independent edges covering all the vertices in F. For any \\(S\\subset V\\) the independence vector is the vector \\(x\\in {\\mathbb{R}}^{| V|}\\) with coordinates \\(x_ v=1\\) if \\(v\\in S\\) and \\(x_ v=0\\) if \\(v\\in V\\setminus S\\). The convex hull of the independence vectors of PMSs of G is called the PMS polytope of G.    Theorem: Let x, y be vertices of the PMS polytope P, and let S and T be the corresponding PMSs. Then x and y are adjacent on P if and only if \\(| S\\cup T)\\setminus (S\\cap T)| =2.\\)    Another question discussed in the paper is the separation problem, which is to decide, for a vector \\(x\\in {\\mathbb{R}}^{| V|}\\), whether x is in the PMS polytope. It is shown that the separation problem for bipartite graphs can be solved by maximum flow algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$B7D8FAE7-5C22-445C-B8CC-0DE95A76E3D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$863156D7-F218-45FD-81FB-212369ECE1B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$58C7C64C-C396-4CB2-A80D-B1D78B129B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$23398597-3728-4C3F-9EFE-B766C1199ABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$BDB42B79-C0FD-449D-9DB6-0D0BA18D2F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$A24044D4-26DB-4384-A7C4-4D46B2A5A10A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"477c180342122b3d3c150b661aa5a8ff6262eced","datavalue":{"value":"4141828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$329DC1C2-35D2-4662-986B-2463E9C28EE4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3cc9fc4c929f69a8a8dd365e93b86583383f819","datavalue":{"value":"perfectly matchable subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$F0DE6820-8677-46D4-AC68-BE3DA119A179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fca7be95f56c8e886763521a06b53397a7f521d","datavalue":{"value":"independence vector","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$4415DB9B-4A6C-4673-AB4D-7011BEA2C81B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$BE6B217F-C68C-4530-B1FB-708F71ABE983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8060896d16b7a947d2d545c9827a67905e8fbcc2","datavalue":{"value":"separation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$8CC255AF-2321-4E63-BFA6-C357E002A2D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$A5BB0118-A2E5-44A8-992B-6C969EF794D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"327c8ceed3def07bd37ff4c6153133e64ff0aaa1","datavalue":{"value":"maximum flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q911485$EC6E488F-C35E-4921-91DE-89F935886216","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":"Q911485$FCCF2459-612F-4473-81D3-B772C03AEED7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d344e0a81aaf04c94e7b0edd2003c2c7f50e0d73","datavalue":{"value":"https://doi.org/10.1016/0167-6377(87)90055-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q911485$A5A39A55-F866-4862-AFEE-3DAC2CAC95FE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba1fb040023271100fcb2bfd7ee329885c74334c","datavalue":{"value":"W2074520661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911485$6D7BAFD9-E53D-4DB7-9BCA-0945FE64AA95","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"86f1036f52c9d084642933ae13a25638be140f18","datavalue":{"value":{"entity-type":"item","numeric-id":3039039,"id":"Q3039039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$C89C9C02-88C4-4C23-B9BB-551492DF1E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$CA03E25A-B886-4EBE-9AB6-4AD2582E4AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$68F19655-7C02-4177-A700-D2D273D467F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$31DA2F18-093F-4436-9C8E-006D7844BD6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"154d468c8b9fe9a919af77166212d00dc5c9c580","datavalue":{"value":{"entity-type":"item","numeric-id":3858023,"id":"Q3858023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$BB4341FD-5BBF-43E5-B79F-296E171BE12E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"317275409be97a7056fb3f62937ae3f09fc39cc1","datavalue":{"value":{"entity-type":"item","numeric-id":796554,"id":"Q796554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$A68E7902-4AE2-4028-8EE8-438DC64FE19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1ba0f71b10e95fd9c744c7f525e1858155d38c7","datavalue":{"value":{"entity-type":"item","numeric-id":3682240,"id":"Q3682240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911485$17A611A1-70D9-40D6-BA09-02E5C9CA108D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"953140e78761f5a30153ad26605c7abfef3039e3","datavalue":{"value":{"entity-type":"item","numeric-id":757431,"id":"Q757431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8039bf16adc5146f7f765393729cf55b808f9ee2","datavalue":{"value":{"amount":"+0.8906917572021484","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":"Q911485$58CC8D70-CC1D-4553-8BFC-2822EA18316A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ba93e63c169f8b9641334f284848b5cf38a238a","datavalue":{"value":{"entity-type":"item","numeric-id":5189879,"id":"Q5189879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46dd554ee5f11a1e9856ca1fe6020985ab1f4bc3","datavalue":{"value":{"amount":"+0.8488529324531555","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":"Q911485$42B8685E-413D-4648-85D4-37AA44E2E994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dbe362a7c76d3ed8038962b33149ca5c1e381d0","datavalue":{"value":{"entity-type":"item","numeric-id":1334957,"id":"Q1334957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec98f1ac260f4e088673f57144e8bacd05579ed3","datavalue":{"value":{"amount":"+0.8042633533477783","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":"Q911485$96401EB1-571E-42F0-9392-94D605A89643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e411d4db046330e98bc8b13cbbea0d02c8d093c2","datavalue":{"value":{"entity-type":"item","numeric-id":2087670,"id":"Q2087670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4381fa4120e598ebc99cc246ac13ed94ad33b7c","datavalue":{"value":{"amount":"+0.8024415373802185","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":"Q911485$AA028E81-3678-4EE3-BCCB-069207F2AE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e19bb09dfbefc6a8496ade833f99198f53b72f7","datavalue":{"value":{"entity-type":"item","numeric-id":681726,"id":"Q681726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78fa21027a728215625f875d720198ecbb855e3d","datavalue":{"value":{"amount":"+0.8024219870567322","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":"Q911485$0E820310-F1E8-4C1F-9B43-2D7A61D516DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_separation_and_adjacency_problems_for_perfectly_matchable_subgraph_polytopes_of_a_graph"}}}}}