{"entities":{"Q397064":{"pageid":398831,"ns":120,"title":"Item:Q397064","lastrevid":56835864,"modified":"2026-03-23T17:52:50Z","type":"item","id":"Q397064","labels":{"en":{"language":"en","value":"Approximating minimum-cost edge-covers of crossing biset-families"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330532"}},"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":"Q397064$15D7BBD4-DA07-4524-88AF-D4EE3D911F57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ddd3f4f21f669cd0e9d3032c637e258d395b9010","datavalue":{"value":{"text":"Approximating minimum-cost edge-covers of crossing biset-families","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q397064$F1C1C589-4A25-4D7F-B9D1-B374EB70D974","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9449c7af7f7d5c6464215496ae461f1c17cf6a1","datavalue":{"value":"1313.05208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$10AA23DE-A1CF-4095-974A-2A07D74BF4DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb558da3b51ce5079c6c609dc76dbfbfe054e7d9","datavalue":{"value":{"entity-type":"item","numeric-id":260247,"id":"Q260247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$2B733B02-2D28-44F6-ACA7-0A3CC794C9DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$25E42726-73E7-4C11-8F25-CC16EEC3669C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q397064$13981131-26D2-4BB7-9C4F-0DD39DA0D9DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a2aabe454aae0dec5486beb22784bf7fd8bafe4","datavalue":{"value":"https://arxiv.org/abs/1207.4366","type":"string"},"datatype":"url"},"type":"statement","id":"Q397064$CAC69DD3-7C60-4A51-98A7-78A864753953","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c75fb6da73ccc7d669eb194755af20bf80d6312","datavalue":{"value":"Let \\(V\\) be a set. Then, a pair \\((S,S^{+})\\) of subsets of \\(V\\) with \\(S\\subseteq S^{+}\\) is a biset on \\(V\\). A family \\(\\mathcal F\\) of bisets on a set \\(V\\) is crossing if \\((X\\cap Y,X^{+}\\cap Y^{+}),(X\\cup Y,X^{+}\\cup Y^{+})\\in\\mathcal F\\) for all \\((X,X^{+}),(Y,Y^{+})\\in \\mathcal F\\) with \\(X\\cap Y\\neq\\emptyset\\) and \\(X^{+}\\cup Y^{+}\\neq V\\), \\(\\mathcal F\\) is \\(k\\)-regular if \\((X\\cap Y,X^{+}\\cap Y^{+}),(X\\cup Y,X^{+}\\cup Y^{+})\\in \\mathcal F\\) for all \\((X,X^{+}),(Y,Y^{+})\\in\\mathcal F\\) with \\(X\\cap Y\\neq\\emptyset\\) and \\(| V\\setminus (X\\cup Y)| \\geq k+1\\). For a family \\( \\mathcal F\\) of bisets on \\(V\\) the family \\(\\{(V\\setminus S^{+},V\\setminus S)\\mid (S,S^{+})\\in \\mathcal F \\}\\) is a co-family of \\(\\mathcal F\\). A directed edge \\((x,y)\\) covers a biset \\((S,S^{+})\\) if \\(x\\in S\\) and \\(y\\in V\\setminus S^{+}\\). A biset-family edge-cover problem is: for a given directed graph \\((V,E)\\), a cost function \\(c:E\\to \\mathbb R\\) and a family \\(\\mathcal F\\) of bisets on \\(V\\) find a minimum cost set \\(J\\subseteq E\\) such that every biset in \\(\\mathcal F\\) is covered by an edge from \\(J\\). The paper presents an \\(O(\\log| V|)\\)-approximation polynomial time algorithm solving the biset-family edge-cover problem for crossing families of bisets. Moreover, if both \\(\\mathcal F\\) and the co-family of \\(\\mathcal F\\) are \\(k\\)-regular and \\(| S^{+}\\setminus S| =k\\) for every \\((S,S^{+})\\in \\mathcal F\\) then the ratio of the algorithm is \\(O(\\log\\frac {| V| }{| V| -k})\\). Some consequences for other network problems -- e.g. for the \\(k\\)-connected subgraph problem, the subset \\(k\\)-connected subgraph problem etc. -- are derived and discussed. Finally, some open problem are formulated and discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q397064$F5CCB972-EA4D-4196-8979-E0118E9979A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$69B646EB-AC4E-4D49-ABE2-E24860DBA8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$138FEF85-C4C5-4D1E-981D-34DDBFDECA98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$19B8A3A7-8874-4402-B7DF-D86E240D4BEB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1b41e4f4014246f4a49dd1a579e0af6e4feb1c7","datavalue":{"value":"6330532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$D3447948-5DF7-4267-81F2-D5312A53E93A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b1dcb9f2cad3045a69835885746c97ce79f23eb","datavalue":{"value":"family of bisets","type":"string"},"datatype":"string"},"type":"statement","id":"Q397064$A681CFC4-33A8-443C-BE89-3DFA5754FA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"960d4c15d1f56d3c4ef331b2e269e24ad66c286f","datavalue":{"value":"approximation algoritm","type":"string"},"datatype":"string"},"type":"statement","id":"Q397064$F66B9FE6-ED38-41F6-B182-A3C64A1B1B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e614187eb9061ac4a9b4cd0bac144385f07673c2","datavalue":{"value":"network problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q397064$DA050AC1-9BAD-415C-8EEB-44340C30C726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q397064$2B3E591D-8B72-47BB-9781-2EA76E414B73","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":"Q397064$0C7606A3-AC22-43DB-8984-C04C4C8EF91E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"90008a65d679b758e199a3e023458572d350dd13","datavalue":{"value":"W2033691165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$D591948B-9D67-4701-870A-645DF6B98BDD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dee00e96fb98204776939907e0b83c5644a53c24","datavalue":{"value":{"entity-type":"item","numeric-id":1941534,"id":"Q1941534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$F090EBC2-3B59-49EE-ADF7-A7B05E188ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31977e72e50f5265ca253000261871a5d3a54668","datavalue":{"value":{"entity-type":"item","numeric-id":2870515,"id":"Q2870515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$DD53E75C-ED42-429A-A12E-35F90A7046F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2062ba53cac7b7d027c61bc58ead165c020960cc","datavalue":{"value":{"entity-type":"item","numeric-id":4429672,"id":"Q4429672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$94569FBF-415B-406D-BCA2-63BAA183522F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cef47a9cb397931fce7efe38edbafe155c13b959","datavalue":{"value":{"entity-type":"item","numeric-id":3549695,"id":"Q3549695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$2A21799F-C653-4440-92C4-4A793E982748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19350378fe8257e657a3bb4eef7c75bb5d6c4d60","datavalue":{"value":{"entity-type":"item","numeric-id":1025990,"id":"Q1025990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$697B97A1-45DE-4E0E-9381-E40783C485A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1066acc47aa019afced1deb4be2ac2683e5934c4","datavalue":{"value":{"entity-type":"item","numeric-id":1898731,"id":"Q1898731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$9F9AA3FF-741A-4C55-AF51-5E09061AD3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db29c8058730e4a340cb2d18fa0c5a817f1aa874","datavalue":{"value":{"entity-type":"item","numeric-id":1892828,"id":"Q1892828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$D403D8CE-7E12-4FCA-A380-90816C09FC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ea6b9fbb293ae0077cfce35426980e21d16a51","datavalue":{"value":{"entity-type":"item","numeric-id":4651489,"id":"Q4651489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$573B3568-2614-4E2D-B608-094C30981DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9ec11393190bba3a25b134c114640881aa42b1b","datavalue":{"value":{"entity-type":"item","numeric-id":5700579,"id":"Q5700579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$5528595A-F93F-4C54-A2C3-D43DFDD8B863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1912419e2fc2f095be0dc3c4820bf7ef33e250eb","datavalue":{"value":{"entity-type":"item","numeric-id":3012788,"id":"Q3012788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$0F4B055E-4DB3-44D6-9908-D655D15AADF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6b9dc7ed5f6848d8eb8c3b75b034b59e538e28d","datavalue":{"value":{"entity-type":"item","numeric-id":1019191,"id":"Q1019191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$884FEE75-E0BA-48FE-8344-A3BC8865DCDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76caa3a03fd47c3e6c09585a2a2ed94aac05ce78","datavalue":{"value":{"entity-type":"item","numeric-id":2896372,"id":"Q2896372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$12A64BB8-DBAF-49CE-BB38-D02BB9A7040F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9c8fc088a5e49d142f0e2d172b778dc51f38f51","datavalue":{"value":{"entity-type":"item","numeric-id":679445,"id":"Q679445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$72F4F597-A75C-4B0F-9DDB-EFFCAE5D5C7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75e65a5402cdab237036b4c82ae75840c96c9ddf","datavalue":{"value":{"entity-type":"item","numeric-id":1849676,"id":"Q1849676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q397064$C16F00A9-3FB1-4368-880D-64C249C85162","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"86f75e4a2ce2ad8a90a0521a20303bc4730d5ad3","datavalue":{"value":"10.1007/S00493-014-2773-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q397064$FA7F3B58-8914-4C9D-9520-7F873DB9412E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df1d63ba3ffd7b1d07341dcd882134c2e6f9e684","datavalue":{"value":{"entity-type":"item","numeric-id":2933629,"id":"Q2933629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcaeec346563ce275dbc182242e2c6febb721fc3","datavalue":{"value":{"amount":"+0.7910029888153076","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":"Q397064$4119677B-036B-4FBA-9EE7-52F22A06BF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f4f313d0520d12370c3fe7f4af9ee3def17b09","datavalue":{"value":{"entity-type":"item","numeric-id":1300055,"id":"Q1300055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4068a169346e159ae9b40063a9cdecea130ff057","datavalue":{"value":{"amount":"+0.7769172787666321","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":"Q397064$A2CC2C81-6F3C-476B-A7CC-E8D39D603C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fabe1354f056e127d7b641df347e532c57486c1b","datavalue":{"value":{"entity-type":"item","numeric-id":789399,"id":"Q789399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e148543b7ffd3f05ca82ddf6d286b5236ebdc43","datavalue":{"value":{"amount":"+0.7703954577445984","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":"Q397064$5A25366A-1CF7-41A9-A6BE-167EFBAED3EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff3e9fe3cb4dcb1b113b574df470944d7ea938bd","datavalue":{"value":{"entity-type":"item","numeric-id":974743,"id":"Q974743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"309c9095bb4ddd70701cb8572214bc285f5713e9","datavalue":{"value":{"amount":"+0.7650566697120667","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":"Q397064$9E430460-4277-40B8-AC85-59C1F5B95F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eec7f01293ffe234c97da08c516144dff180913f","datavalue":{"value":{"entity-type":"item","numeric-id":873653,"id":"Q873653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0048bf646f924fd68a2bc43299b217c3ea1a8542","datavalue":{"value":{"amount":"+0.7611229419708252","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":"Q397064$82D1DE97-E20B-4E10-BA36-2966EB6E3A5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:397064","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:397064"}}}}}