{"entities":{"Q1090461":{"pageid":1101213,"ns":120,"title":"Item:Q1090461","lastrevid":49072600,"modified":"2026-01-06T13:35:39Z","type":"item","id":"Q1090461","labels":{"en":{"language":"en","value":"On-line updating of solutions to a class of matroid intersection problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4007738"}},"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":"Q1090461$5F433799-C551-438F-A824-0801D89B93D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf2c4948b7ea14171c5458f11ace11b7573326fc","datavalue":{"value":{"text":"On-line updating of solutions to a class of matroid intersection problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090461$ABE95FE8-773A-4047-A575-2472F95E1C3C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2446855fd39bcc01723bf90b8b23155fb6f13f3f","datavalue":{"value":"0621.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$18A03D9D-DD66-4134-AFD5-C0A8646BC0A4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a304751d8cf55d6b4a725b1492a27e0133d24f7","datavalue":{"value":"10.1016/0890-5401(87)90027-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$FB0F412E-48D3-449B-AC64-2AD921C9C308","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3d27020ae42071ce34c2e2b260b922db4110865","datavalue":{"value":{"entity-type":"item","numeric-id":215688,"id":"Q215688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$34AD868A-1421-4982-AEDB-6C8C06188A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61673cd7a5e59d3f949e35f78d2ca9d4f3125ae3","datavalue":{"value":{"entity-type":"item","numeric-id":1090460,"id":"Q1090460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$44A41D35-DFA5-4903-9D93-1AABA125A518","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$0ED3606D-ED41-49F0-9B35-CE198108728F","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":"Q1090461$4AC10B7B-D30B-4441-8CBA-AEFF8E276E01","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"51e0efd454551ea725ca7abefc07313a3018e8ec","datavalue":{"value":"The class of matroid intersection problems is considered in which one of the matroids is a partition matroid specifying that exactly q elements in the solution must be red, and the rest green. A characterization is presented for how the solution changes when one element changes in cost. Data structures are given for updating the solution on-line each time the cost of an arbitrary matroid element is modified. Efficient update algorithms are given for maintaining a red-green minimum spanning tree in both a general and a planar graph, and a red-green job schedule for unit- time jobs with deadlines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$98402420-5BBC-426B-9289-63B91FA45B7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$D7C3F104-8594-4B83-807F-7D9B8EA781D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$1F398F0B-5BB1-4FFC-A3A8-B07BB00FB161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$B6884AE3-9FAD-4DA1-ACDB-6D3E2C926C63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d33550b6e4a97a9101031df25d8cfbe55ed6265e","datavalue":{"value":"4007738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$B96F5C67-6E43-4CE3-870B-C9DFE37B06AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec154bc44d406185373f22e33fac5d0165ab43cb","datavalue":{"value":"partition matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$20D96292-F40B-4D34-BF15-B6823D24CA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"135a7e6e28c5e714d2a4204296bc6a14edbd680e","datavalue":{"value":"Data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$6C5AE621-8CF8-435D-82BE-C50F3276D628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e797a87e6763e7ed490dc26e379f4977a5ce66bd","datavalue":{"value":"update algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$67F5CC4C-494D-4D05-BA9B-360D3A5EE025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f1cda9e146ebe1cfdbac78296b16450fcc9e0c","datavalue":{"value":"red-green minimum spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$7E308F59-15FD-48FA-8A61-7B1E03AC4D11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$F61ACF07-D0FC-44E1-A9FD-9972B2823128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e874aa5d088cbe647ac268be9f300d992a89015","datavalue":{"value":"red-green job schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090461$E0E8D846-8876-41C7-A7E0-F56AC3363C41","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":"Q1090461$94272A1E-9D15-4FC7-8D51-DB207E330F44","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a46a3d0bbf9e0d9a92802de3f00292d6475e1fb9","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90027-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090461$BBCCCA22-5335-40A4-85E6-2093766E64C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"499fa979500311a0c329b59948034ecffd79b2a0","datavalue":{"value":"W1968928800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090461$22E5C872-78B5-4FCB-AC04-EBB42A40179D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f50bb2463f68a38c17b8200f5931261dc0c5e7e","datavalue":{"value":{"entity-type":"item","numeric-id":4132283,"id":"Q4132283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$1F55DC63-7690-408C-9E5F-EB82B892CEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0a13a8417673f45e28aa7499e1e7b9d7bfca27","datavalue":{"value":{"entity-type":"item","numeric-id":3694711,"id":"Q3694711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$A5B9A553-5B9B-45BE-B66B-9D294BA36E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00a1e2e0c5334dad3a0bd73a779036df7e15c686","datavalue":{"value":{"entity-type":"item","numeric-id":3682487,"id":"Q3682487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$9A3E6400-53F2-4650-9DF9-C955A3195CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9beef10f14c1534c9b646b394bb6806fa6bcf5a6","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$1B4D6648-BDBA-4C92-9A4F-4CC7BB833B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7935a7a1b24b294effda507df33849d1fce1c2","datavalue":{"value":{"entity-type":"item","numeric-id":5574593,"id":"Q5574593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$DAD9AD23-D090-4906-A0EA-2D0BFADF48C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1a7e29801581e9e5a5187db25cd480c84107d91","datavalue":{"value":{"entity-type":"item","numeric-id":793743,"id":"Q793743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$91C637DC-FB21-4A3B-BC3D-C4ED70859611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72094fe196507e2a340258c54f5422806cfbb3ff","datavalue":{"value":{"entity-type":"item","numeric-id":1220871,"id":"Q1220871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$451329F3-BDDD-4EC3-8B0F-244D77B1DD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$3F12006C-D4FE-4C1E-B368-D0124223B401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17f12332ca89ec48bfc3d5560520efcbd09cf4","datavalue":{"value":{"entity-type":"item","numeric-id":1145508,"id":"Q1145508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$0DD2B3D2-A052-49BF-98C9-D2BEF0A2CFC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$8C4DFFDC-B929-454E-B9E6-76B4160B3CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b76c498f5c4968b18e0a5cf8a7bb4513c31822","datavalue":{"value":{"entity-type":"item","numeric-id":1838310,"id":"Q1838310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$01218A93-1229-4FDC-972E-B30334C61B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$6DAF4671-C17D-4876-8D13-CAA277AD652A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db8343e526f156f1469a28b5688ff6513e9b7246","datavalue":{"value":{"entity-type":"item","numeric-id":3678701,"id":"Q3678701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$5F6EA072-788E-46BC-BF55-980FF687019B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90982d7813495812818b90d95d5cde9a55d1f5f","datavalue":{"value":{"entity-type":"item","numeric-id":3766892,"id":"Q3766892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090461$F5297B53-0755-44AF-AC9A-A672AA971A0D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d049b2867fc19c693dbf3c93c07edd6cb2817ab","datavalue":{"value":{"entity-type":"item","numeric-id":3823151,"id":"Q3823151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"069c7200f05746944049ab8045c09268852c02f1","datavalue":{"value":{"amount":"+0.854758620262146","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":"Q1090461$88F5256F-364D-493D-B474-ABB8E70F9395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61ec7d4ece6914eaa7e4b7017b769b27da7f4b7","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7502984a6f5a8e0681a4db3d178d7bb1e216094b","datavalue":{"value":{"amount":"+0.842603325843811","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":"Q1090461$43E62F1B-85FE-4921-A58C-256A78756A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a28c9a2d577fc104a706984364e831f3937ef9ec","datavalue":{"value":{"entity-type":"item","numeric-id":3682487,"id":"Q3682487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"874380e9f187d17a49e4286cc0b0c0f4e90c6491","datavalue":{"value":{"amount":"+0.8046977519989014","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":"Q1090461$462518EA-92C1-4C5D-BF46-B01C75ED28C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6ee458666986c6c42953ceb23507a291d64eb52","datavalue":{"value":{"entity-type":"item","numeric-id":3694711,"id":"Q3694711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f99c722fadf77af4674088b3cf33d9f657b9f1b","datavalue":{"value":{"amount":"+0.7872365713119507","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":"Q1090461$88A12A16-F3B2-4DDD-8E5C-DDF3B2C520FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"789134e386691c82d11a18e56260bbbde78d7aa9","datavalue":{"value":{"entity-type":"item","numeric-id":3698812,"id":"Q3698812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b11db53655953ee7fa6d13f8d9fcab1a4bb7763","datavalue":{"value":{"amount":"+0.7801957130432129","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":"Q1090461$BCD9B8DF-1DD5-4B88-BE5F-ADE0C8820EE1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1090461","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1090461"}}}}}