{"entities":{"Q582183":{"pageid":583950,"ns":120,"title":"Item:Q582183","lastrevid":62936334,"modified":"2026-04-11T09:05:46Z","type":"item","id":"Q582183","labels":{"en":{"language":"en","value":"Median linear orders: Heuristics and a branch and bound algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4130138"}},"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":"Q582183$5178A0DC-B540-44B8-A7D7-B9027A71A4BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45c1ddf8d0f08774b55d179b2a2edb0397f85db4","datavalue":{"value":{"text":"Median linear orders: Heuristics and a branch and bound algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582183$22BFB774-1AE6-4D1F-B319-5A43669154EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f26a5c90f2594103d555eb060f0171e5f4c335f","datavalue":{"value":"0689.90003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$CCD04C5F-5D36-40F5-9E85-FE8B2DE074CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e4ced1cb24fb7d08f34e5abcea7784ce9b9f7818","datavalue":{"value":"10.1016/0377-2217(89)90442-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$DF8D7E72-1837-474B-8BC1-D98420537C1A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a1b7c76d48bb1e0dac160345f59745fc2a059b6","datavalue":{"value":{"entity-type":"item","numeric-id":226963,"id":"Q226963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$34C24DB9-E4C2-4ED6-B602-A5AA5A78C59A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce7a558653b50b607f618f4567b1430b29267949","datavalue":{"value":{"entity-type":"item","numeric-id":922252,"id":"Q922252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$2E5C5E48-BA35-45E4-B453-E45ACFF5CBA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9bac267563fab4bf2dbfa23cadee42ea5f95e14","datavalue":{"value":{"entity-type":"item","numeric-id":263300,"id":"Q263300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$4099A659-02E6-47C1-9F83-5E034D2A9070","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$7939435C-CA44-4E47-95F9-664E3888EA04","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q582183$A2565C88-282D-4370-BC65-12DBEC8AE922","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ef953abc17644fae919d30a875bacc9dd9ce24c","datavalue":{"value":"The first part of this paper illustrates the relationship between median linear orders and the so-called minimum arc set problem. In the second part a heuristic is studied to solve the minimum feedback arc set problem for non-weighed tournaments, which is then extended to the general case (weighed tournaments). In the last part, a branch and bound (b \\& b) method is designed to get all median linear orders associated with a profile of linear orders.    Among the advantages of the b \\& b method are: (1) whereas most methods are only able to compute just one median linear order, b \\& b computes all of them; (2) b \\& b always provides exact integer solutions; (3) the algorithm for the b \\& b method can be easily set up on any microcomputer for reasonable sized data.","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$4E850ECC-ACC7-4F81-BAAE-2D9D13D5A0BC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f3f6c5c22a124c33ba56393a2ef847c4c1e5f0b0","datavalue":{"value":{"entity-type":"item","numeric-id":593637,"id":"Q593637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$6EBA95D5-9FDD-4AAA-BD52-627BE88AD8E5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7dfd8303bd13aea2e4b7120171f58bea1dddf5e5","datavalue":{"value":"91B08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$229F8630-A39A-4375-B2E0-5884BE7E06AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$EB13A3EC-D294-400C-8D57-3C769EB9A91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"306e8f65eab4f086795d9337f8e86ca94ed2db57","datavalue":{"value":"90B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$7E05EBCA-23DC-4A8B-AA9F-8A52BDEB8D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824cfdf2b129d72f7287008060b5bf497f3b4f34","datavalue":{"value":"91B14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$2DB59C78-D8CB-4C70-BE48-0D2DF3103313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"418d4d19aa7c87e33d52e580c9c108a1bc2de096","datavalue":{"value":"90C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$D59A6CDB-882A-47CA-A205-D903F7A95CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$9854866D-044D-4F4B-8A00-5DE1D1B90DE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e5284f632ad6f9ce5c040fe27f646353a904095","datavalue":{"value":"4130138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$9834DF6D-A940-4C06-968A-028B75659231","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$C04C415A-D936-4374-927F-45A712E27979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"080b5701800fed9a8de5c1231a39099833480668","datavalue":{"value":"multicriteria decision aid","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$945E83C2-C462-45A0-A5D9-3EC96ADE4CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a13f4cc471fe4b3e1a9e9a1f21c8d8ff1f85627","datavalue":{"value":"median linear orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$5BC04A9D-5027-4892-B04D-13EAE34A150F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a34728da53cae2c674aee2a890ca7bcd113e270a","datavalue":{"value":"minimum arc set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$271CE5A4-191E-4556-9935-600564D117E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60b8bb34449aca94c545756bc6197e37504369b0","datavalue":{"value":"minimum feedback arc set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$2A8B9958-37DC-4132-B2CE-D89E005FBB2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33c8629cfacde6a49201487cca181efb35086498","datavalue":{"value":"non-weighed tournaments","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$1642ADAC-7E44-45AE-8747-C707DF70FD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q582183$5EC70A3E-9536-41A9-883A-7AF03F4E5E5F","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":"Q582183$1BEA51E3-CDD3-48E5-A33C-79E4BA809239","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"066004da0a75c320c1b40402fb47ac499244e396","datavalue":{"value":"https://doi.org/10.1016/0377-2217(89)90442-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q582183$1BD7FFCF-190A-4839-B70C-A4EF850CFC12","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc3cc5b02cd5d1d878b6196183b600be461c6582","datavalue":{"value":"W2089788538","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582183$42A4C16D-A4D5-49A2-8F5A-D5EAD22D8065","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d093787d669b091c2e3a9dd916b22f1be82962","datavalue":{"value":{"entity-type":"item","numeric-id":2783476,"id":"Q2783476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$E66671BE-EAB9-4E09-BBB7-40FFE1CF4974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96a479e0e873bf0d20c385f02d6f2bcffa49a7f1","datavalue":{"value":{"entity-type":"item","numeric-id":3879000,"id":"Q3879000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$BC770B18-0E6E-4EA0-A6B9-2565C40A58D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93512bfdc47afc24e7dc7bba727163eb15783f98","datavalue":{"value":{"entity-type":"item","numeric-id":1164937,"id":"Q1164937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$F399DCE6-B3C0-4274-B968-EE6DAE00B84D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be32dd08355b219aedae9f7f550e12f7b99bb0b6","datavalue":{"value":{"entity-type":"item","numeric-id":1120433,"id":"Q1120433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$747ECE48-6B7C-4CC5-A8F7-0324A7BEBB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0af4fe52341c202d0973cb222cce48713289bb","datavalue":{"value":{"entity-type":"item","numeric-id":3757648,"id":"Q3757648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$DF47B7E3-B663-4E66-BB9B-25FF683B2496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ac967abbc07857f5b4fe2a3aca34b920081f768","datavalue":{"value":{"entity-type":"item","numeric-id":5582743,"id":"Q5582743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$E0682BAE-270D-40FC-8728-E139F50A794C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0770d23ed9d64e41e166a3d1f35c5e1388bc1f63","datavalue":{"value":{"entity-type":"item","numeric-id":3698818,"id":"Q3698818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$19F6DDE3-B2AA-48FB-9624-8100211514FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43fd43796a032f8fa1d835740fdfb8c1f13e3234","datavalue":{"value":{"entity-type":"item","numeric-id":3698819,"id":"Q3698819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$0B07347C-885D-4E47-97DD-4CE93683014B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bc7ef18248a47de99db1d82163e295f40678cdd","datavalue":{"value":{"entity-type":"item","numeric-id":4128286,"id":"Q4128286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$DA8F9E06-4F88-45EC-87F3-1F0782B7A943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05bbee9ff86b2a9c6fc01bcb7683b12933da168d","datavalue":{"value":{"entity-type":"item","numeric-id":3272318,"id":"Q3272318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$9FBAD6CA-5843-4E40-89F2-04DD86853CE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"446ead8286b2e67ce1667abb498092e0e390909c","datavalue":{"value":{"entity-type":"item","numeric-id":1154950,"id":"Q1154950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$878529C2-8B37-48BE-A4F0-180312ADEAB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$9CDBE6EA-2532-48CB-9FFE-7ED8D68A1E02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"793048a14358b8cbcf5371f83ea1a4f7146c9cc4","datavalue":{"value":{"entity-type":"item","numeric-id":3215236,"id":"Q3215236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$36D1C3EC-A4AA-428C-B8D2-7BA34725F2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4352b8b2a1f08a39b878b0b4f0b435e884f3b60","datavalue":{"value":{"entity-type":"item","numeric-id":5585195,"id":"Q5585195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$0E95004A-1477-419C-A134-D7F4AA368CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d56bb72142e0045761662706affa99c3f61f4999","datavalue":{"value":{"entity-type":"item","numeric-id":5512580,"id":"Q5512580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$65EDB7A0-E2F1-417A-991B-57E38BC48D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c341b3be59bb3ca0f3d4614aa9ada6b1dc4bdd27","datavalue":{"value":{"entity-type":"item","numeric-id":3038367,"id":"Q3038367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$3CA315D4-0AB4-4110-9BAB-3860B6B56D4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12ef07c96efcb62b3d0eb51b255877bd24b42dda","datavalue":{"value":{"entity-type":"item","numeric-id":3745273,"id":"Q3745273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$5D44CD5E-CAE7-4F7D-87F1-45A5701AAEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e866703c8feb494814bb9ed59bd2fa74a4935ef","datavalue":{"value":{"entity-type":"item","numeric-id":4166483,"id":"Q4166483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582183$3BB32D70-EC49-419A-919F-E1CBD271EC1F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e8fea9033dc42ccf8410fb7b0a04ef337ac5ab8","datavalue":{"value":{"entity-type":"item","numeric-id":1356737,"id":"Q1356737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b7c0b620ae3b894ec9091ea12ef342ac04185d2","datavalue":{"value":{"amount":"+0.8606512546539307","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":"Q582183$649F881A-2763-4E73-8B79-E8FE83148D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9f89779b2428a2e887249c161fa638070973fcb","datavalue":{"value":{"entity-type":"item","numeric-id":2433800,"id":"Q2433800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91887f801700429db72ca51add78208775501344","datavalue":{"value":{"amount":"+0.8465473055839539","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":"Q582183$9265C212-844A-4983-8660-993884638A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bdbd2f6e53d538830a815ea28b7fd60fc07354d","datavalue":{"value":{"entity-type":"item","numeric-id":4878464,"id":"Q4878464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac99e4e5de7620742255639c35075813efad5e4d","datavalue":{"value":{"amount":"+0.8123309016227722","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":"Q582183$CB0F4144-A0D2-4E7D-BC92-C304B4190811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"395757972db471cb1d6716d3b5b894488e1e7d53","datavalue":{"value":{"entity-type":"item","numeric-id":4339964,"id":"Q4339964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41aa304e5985cffa99233bebe6f2427c69e09b9a","datavalue":{"value":{"amount":"+0.8025609254837036","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":"Q582183$E57735B1-7875-4C84-8886-9B60135634E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec723c0e1309539f178ac27b60b26c23d59ae437","datavalue":{"value":{"entity-type":"item","numeric-id":449031,"id":"Q449031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b5efc03a6e86583516f1c95a4db746974744ea8","datavalue":{"value":{"amount":"+0.7802428603172302","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":"Q582183$781CCD06-C4FA-4784-8696-4704941C5A47","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Median linear orders: Heuristics and a branch and bound algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Median_linear_orders:_Heuristics_and_a_branch_and_bound_algorithm"}}}}}