{"entities":{"Q1108202":{"pageid":1118951,"ns":120,"title":"Item:Q1108202","lastrevid":66146136,"modified":"2026-04-12T07:51:25Z","type":"item","id":"Q1108202","labels":{"en":{"language":"en","value":"An extension of the K\u00f6nig-Egerv\u00e1ry property to node-weighted bidirected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066653"}},"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":"Q1108202$3A48028E-008A-45CD-8ABC-6F0EBEA73D98","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51067b62a3c2e7a74b43e85d14cbd5035bc269e5","datavalue":{"value":{"text":"An extension of the K\u00f6nig-Egerv\u00e1ry property to node-weighted bidirected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108202$D89E2779-D176-43AB-BFAB-1F169703CAB1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b09a9916231d63fc1cb5d9172d28ceb2a9f0170","datavalue":{"value":"0653.90083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$314F87CA-6782-4739-97B6-2C706332079B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e98abaca5a1bbccc350b2208f31dbefd5beba894","datavalue":{"value":"10.1007/BF01580775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$B56E8FEB-6351-4E0A-9BB6-CFCB74328D5B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3fa7468e26ae0990504df1ad1526b1301a8318b","datavalue":{"value":{"entity-type":"item","numeric-id":958100,"id":"Q958100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$7202BB2E-7671-4A12-AB64-5EA7B8B00459","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$99A4703E-9D1D-417E-A4CC-729151F6CA47","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1108202$05F45D2E-2BCF-4FCF-BED2-E85C70BEE70E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d31f170a38a8cc761820cc48599fdd57a6a2c0ca","datavalue":{"value":"Let \\(G=(V,E)\\) be a connected, finite, undirected graph without loops or multiple edges. If the number of nodes is n, let \\(b=(b_ j)\\) denote an n-vector of positive integral weights associated to the nodes. The author considers the linear program  \\[  CSP:\\quad \\max \\sum^{n}_{i=1}b_ ix_ i,  \\]  subject to \\(x_ i+x_ j\\leq 1\\) for every edge [i,j]\\(\\in E\\), and \\(0\\leq x_ i\\leq 1\\) for all \\(i\\in V\\). In an earlier paper by \\textit{J. M. Bourjolly, P. L. Hammer} and \\textit{B. Simeone} [Math. Program. Study 22, 44-63 (1984; Zbl 0558.05054)] some results and two polynomial time recognition algorithms are given for CSP having an integral optimal solution (the K\u00f6nig-Egerv\u00e1ry property). In the present paper this concept is extended to mixed graphs (having both directed and undirected edges) and bidirected graphs (whose edges have two heads, one head and one tail, or two tails).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$862E9CFE-374B-4840-8BA1-1A0A02D360F6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$D5269A31-4869-4818-8BFA-6D36A047554C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$487ABB3A-D67C-4800-9758-A6D1AAAA289E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$346B7EC3-EEFF-4172-B594-6EDB5AB91967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$8020FDD8-5990-49A8-A4CB-169B97940732","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab54690fd9d8f71887d4af0134fa65355268f926","datavalue":{"value":"4066653","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$49BBB310-F12F-4B15-8357-C2420A4FCCC9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b8a044997b47d361e8c908be3f482dd59614ff","datavalue":{"value":"node packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$78936B17-B831-4E89-9F67-143FF90AB4F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e87618aee6343e13e99830120698ef319daa4c9","datavalue":{"value":"integer linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$C1741F33-92FD-4BCD-9E9E-F8B4958C64E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$0FC49680-FADC-4478-9DE9-9293FE93C5C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"874956b700dd54c4216782635162f84e2a03b252","datavalue":{"value":"connected, finite, undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$13316DFA-9079-413C-BA02-3BDD75963C39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"640a4fdb90407b4c41692a7c8e8bd20dd69a4a9b","datavalue":{"value":"polynomial time recognition algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$3F99671C-060F-4A83-A7D7-FF7BF45A336A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ece06ad70ebaaa49c5b15f0d8034074815a3cd72","datavalue":{"value":"K\u00f6nig- Egerv\u00e1ry property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$DBFB95EC-D0B0-4808-A4F3-7030873A1E60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0de429593140647dc3a596da860845a1c045f74","datavalue":{"value":"mixed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$57BA8165-D056-4743-84FA-105A3110407A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d14dd841cc420c71df045f0f822fcdd120df181","datavalue":{"value":"bidirected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108202$F32603E7-BC66-4DD9-9952-AA4C944965FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a045f63318f1de593d90eef7099e020a13de6579","datavalue":{"value":{"entity-type":"item","numeric-id":593501,"id":"Q593501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$D4BCD361-A864-45DD-BF22-FFDBC867460A","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":"Q1108202$E40770C3-A909-43E1-8B19-6B17C983B462","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$FB8C7749-2EBE-4961-8B70-6AD7B7835E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8ae8bf01f116bb5adf895448a8445209d5be78e","datavalue":{"value":{"entity-type":"item","numeric-id":3222885,"id":"Q3222885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$B4419853-0B90-4FCC-809B-3EADFC9DA4B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271059027ec9c0e0491187496cb25dd92d2df81b","datavalue":{"value":{"entity-type":"item","numeric-id":5675543,"id":"Q5675543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$41D66875-7963-46BC-9EC0-222D114A3559","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":"Q1108202$18B6558D-B880-47BA-8641-A7568E81E903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b729c59c35fddf439c375e22693e619ce36a3b7a","datavalue":{"value":{"entity-type":"item","numeric-id":1180424,"id":"Q1180424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$6344E649-C263-4466-88C2-B6619438A087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1e239dce14973bc963cb9871e26501ddc153e9","datavalue":{"value":{"entity-type":"item","numeric-id":3693267,"id":"Q3693267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$A2C130FD-804F-4575-AB4D-4F26770FA06C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3785a174202564998e1034d8e8fd719b92d2ff9c","datavalue":{"value":{"entity-type":"item","numeric-id":3968760,"id":"Q3968760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$41CC893F-FF81-4ABA-A692-92AEF2315103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d1492ebdc5b2ceb0ca4c85fc9ed7bee8f4792bd","datavalue":{"value":{"entity-type":"item","numeric-id":3968758,"id":"Q3968758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108202$8C40572F-7368-4DFB-B295-CC6843B508D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f3116334512886e71bb1c9629130e96091ecc610","datavalue":{"value":"https://doi.org/10.1007/bf01580775","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108202$5CB85746-E500-4825-9F91-5BBE8E9F20D8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de55d1e7b53247fbb61af29bb0c8c7ec9a23e707","datavalue":{"value":"W2066441105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108202$5FFA317F-2E57-41C3-9E1B-A7FDB605015E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f3df9f1e5b620fe295b58ddd5cc0e750a094e1f","datavalue":{"value":{"entity-type":"item","numeric-id":3222885,"id":"Q3222885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e8b67a3d9171f4782b13f663f528d183c0a92ac","datavalue":{"value":{"amount":"+0.8148397207260132","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":"Q1108202$B724F859-C60E-4961-9369-ECD76035874F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0e64213e0fc6ab8102801aa1327a55af2c25750","datavalue":{"value":{"entity-type":"item","numeric-id":802627,"id":"Q802627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44c194b99a42ac9d25dcaa03c67c588ec1453ab2","datavalue":{"value":{"amount":"+0.742350161075592","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":"Q1108202$700F6701-6D1F-447B-9F86-C1AC99A61CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1497ba0087ba3be4bc8bdf02efea929621a57ad2","datavalue":{"value":{"entity-type":"item","numeric-id":4366150,"id":"Q4366150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"970cd33926c6a57c8c4536ef81c59497858e27b5","datavalue":{"value":{"amount":"+0.7318693995475769","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":"Q1108202$5E3C5949-9661-4A83-89FA-28F51E9454D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d5c6181e84fe5885fbcffb7a0e1f6f27880668","datavalue":{"value":{"entity-type":"item","numeric-id":1813951,"id":"Q1813951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e23401a8ad73298ade00511caf98eaa908299c61","datavalue":{"value":{"amount":"+0.7293123602867126","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":"Q1108202$D1A55130-6715-4308-9B49-6E0921AB8231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8463c887181286d682a1528c0ac03259f339fc43","datavalue":{"value":{"entity-type":"item","numeric-id":1869226,"id":"Q1869226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e23401a8ad73298ade00511caf98eaa908299c61","datavalue":{"value":{"amount":"+0.7293123602867126","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":"Q1108202$AF3139E8-B4E7-4397-9E29-49C4AF7D30FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extension of the K\u00f6nig-Egerv\u00e1ry property to node-weighted bidirected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_extension_of_the_K%C3%B6nig-Egerv%C3%A1ry_property_to_node-weighted_bidirected_graphs"}}}}}