{"entities":{"Q1272485":{"pageid":1283235,"ns":120,"title":"Item:Q1272485","lastrevid":68347218,"modified":"2026-04-12T23:06:01Z","type":"item","id":"Q1272485","labels":{"en":{"language":"en","value":"An efficient algorithm for minimum-weight bibranching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1234266"}},"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":"Q1272485$8E9ED3A9-A872-432D-A117-DC79AD9D00C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f7b82746b78e5e789a30877ec6a83083aaf99aa","datavalue":{"value":{"text":"An efficient algorithm for minimum-weight bibranching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1272485$C304B005-76AB-4C09-AB49-90E493ECBB54","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8d91827966944027cb0289fbd75d6354ddbc697","datavalue":{"value":"0916.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$B1D01D83-18F5-4DB3-9FAD-E19F5D91DC75","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$5F6E5C5A-9E9F-4F5B-B4DF-97AD4836C7AC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6094f3d127c088853e8107203d6bdf198a3687af","datavalue":{"value":{"time":"+1999-07-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1272485$A493A8F9-04F6-4764-83F7-4AA27D90FE4A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"79f6652e4be515d67e649e2b3950878f8d3f3638","datavalue":{"value":"Let \\(D=(V,A)\\) be a directed graph, \\(S\\) a subset of \\(V\\), and \\(T\\) the complement of \\(S\\) in \\(V\\). A bibranching in \\(D\\) (with respect to \\(S)\\) is a set \\(B\\) of arcs such that for each \\(v\\in S\\), \\(B\\) contains a directed path from \\(v\\) to a vertex in \\(T\\), and for each \\(v\\in T\\), \\(B\\) contains a directed path from a vertex in \\(S\\) to \\(v\\). If \\(S=\\{r\\}\\), a minimal bibranching is an \\(r\\)-branching, a directed tree rooted at \\(r\\). The authors give a primal-dual algorithm that determines a minimum weight bibranching in a weighted digraph with running time \\(O(n'(m+n\\log n))\\), where \\(m=| A|\\), \\(n=| V|\\) and \\(n'=\\min\\{| S|,| T|\\}\\). This algorithm obtains the best known bounds for two special cases of the problem: bipartite edge covers and \\(r\\)-branching.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272485$843C9096-4E16-4F41-9BD2-BFDF8B4F7F4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$25D90328-D392-47E7-9DCC-204FAE990A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$EDCF4F73-567D-4E96-9804-00D492E8C5F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$43776B0B-3208-4969-AF4B-F04326D02449","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3e1460b102169c095aa86be2e0271cecddc1879","datavalue":{"value":"1234266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$BD5099F6-1F89-4A69-B42C-143AB73D0548","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"523fd32c235ce1b1f6f86fda4aadd7b778587330","datavalue":{"value":"\\(r\\)-branching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272485$5DBF93CC-4B80-492E-A664-6EDC180FAF25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"254454aeb1eccb9c8aa59c556bb7c0e16090b9df","datavalue":{"value":"bibranching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272485$8E5807F2-2942-461A-8F45-63B31F13EE42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49b214501ed6da825da702506d1e3cd3a85b4745","datavalue":{"value":"directed path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272485$F9734537-3E9C-4B8C-9FB1-BE65D5BFB3FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bedc1511384786d6ec49ae20f5d21348fcf0177","datavalue":{"value":"bipartite edge covers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272485$9B86A14A-2C5A-4A64-8BDD-4C737307A2FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"037eb965a3bd3b6e1066264d21e0687b64f8d96d","datavalue":{"value":{"entity-type":"item","numeric-id":486620,"id":"Q486620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$F83C4F00-7238-4383-9C46-933FF0CF92B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea6097f37f57d3179aa66fde4b712d1e2ad96ee4","datavalue":{"value":{"entity-type":"item","numeric-id":313450,"id":"Q313450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$660CD91E-FDF0-4F48-B9B0-C1E7CCA80DB3","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":"Q1272485$2837C854-85B4-4981-8870-03FB2919D295","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cc03a00a917b29819c87ac4773ad0d1f1ec32f5a","datavalue":{"value":"https://doi.org/10.1006/jctb.1998.1817","type":"string"},"datatype":"url"},"type":"statement","id":"Q1272485$CB8DD876-B054-400A-9A4C-904B5F002415","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"29002b887cd24ef74482da2d9c553b648fcf810b","datavalue":{"value":"W1981881379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$AC330E2D-C59C-4D9F-8617-EFC7B5999D0E","rank":"normal"}],"P223":[{"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":"Q1272485$F3D9B946-2498-44E3-A42D-7C5B9BC8C190","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":"Q1272485$844BB93D-77DA-47E5-AB7B-9F6D91FA3765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$91D7EFEF-4707-4375-A263-AECC992050C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$E6C2AC1F-D376-4FF8-BF0D-D24B4FB557B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d601b5a73aa3f981ed43e68477a6afb0b2f45837","datavalue":{"value":{"entity-type":"item","numeric-id":1086246,"id":"Q1086246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$E33A2212-2826-4177-950D-4C1BD3E583C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29334cbfed323135d41d245a3ecf67c8d4aa6b93","datavalue":{"value":{"entity-type":"item","numeric-id":3922478,"id":"Q3922478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$26248840-AD91-466F-B779-34EF6490E388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a80c97696626b314d5b2bbf78ff20ef6ce2b2693","datavalue":{"value":{"entity-type":"item","numeric-id":3922479,"id":"Q3922479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$C3523878-F0D3-4CA0-B26F-BEBA65FDCD84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad7c90f04ab32aae2e758bb7a13353149f66448e","datavalue":{"value":{"entity-type":"item","numeric-id":3922480,"id":"Q3922480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$02951645-E6C3-4D35-97AF-B14A2289151A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49308b1e0034e9584c579e0421111ba387485e11","datavalue":{"value":{"entity-type":"item","numeric-id":5519710,"id":"Q5519710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$E058602D-979E-4669-9608-7DD18590BA38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c401dbe104705de719d56e47bb57853d326cd99","datavalue":{"value":{"entity-type":"item","numeric-id":3960724,"id":"Q3960724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$0A7DB28B-48CC-414A-AEC9-BB294127BA37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a0c31c2d698467d582f5e1c980108ce54a1d3d8","datavalue":{"value":{"entity-type":"item","numeric-id":5668591,"id":"Q5668591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272485$2740379A-09FE-4CD9-A964-0A868A56FB39","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a69c0c3a94bd860ec35242a1a4b000e2b942f4ae","datavalue":{"value":"10.1006/JCTB.1998.1817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272485$0E07514D-0179-4DC7-AA4A-A92D2C3A9136","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d318a513c9ecece4c13a3f04bf3b34ba97c96074","datavalue":{"value":{"entity-type":"item","numeric-id":3596721,"id":"Q3596721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb3d01b46d816d4f1cbf40cc2df4ad7400944f1f","datavalue":{"value":{"amount":"+0.9342681765556335","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":"Q1272485$9B86A438-40EE-4E5B-AF27-CA770D5A97FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d3af1f83acf844266988a42590d11cb5a213d56","datavalue":{"value":{"entity-type":"item","numeric-id":652532,"id":"Q652532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9b70e566c84092d210acbe5096d1f72ec6a0728","datavalue":{"value":{"amount":"+0.9289631843566896","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":"Q1272485$7067746B-C9C5-4C63-8054-060D1F86B533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0154539f6b58ba2ab7c3b5ca374769921067bd0d","datavalue":{"value":{"entity-type":"item","numeric-id":4831831,"id":"Q4831831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2731f0b62a84bc78b2bc30cf2c12a615254584bf","datavalue":{"value":{"amount":"+0.8282124996185303","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":"Q1272485$C3C19738-7476-4291-A458-FE7500721343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9362e27958a331f3c8c3ad44df6682c6c5cce4f","datavalue":{"value":{"entity-type":"item","numeric-id":2024606,"id":"Q2024606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b146b96c9bc8d5867b93104223a3fb359f3fe012","datavalue":{"value":{"amount":"+0.8011972904205322","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":"Q1272485$DBB97441-A22F-4781-8FDA-A94900D0AEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"838eac088536122c6fb60a67142be08a60d1ec8c","datavalue":{"value":{"entity-type":"item","numeric-id":2192110,"id":"Q2192110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ec53de136e11016c95d2e93a59eb10d2c1f4c66","datavalue":{"value":{"amount":"+0.7886045575141907","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":"Q1272485$02AE0E31-8279-45BD-A6D8-2F2EB9BCE9BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient algorithm for minimum-weight bibranching","badges":[]}}}}}