{"entities":{"Q751660":{"pageid":753509,"ns":120,"title":"Item:Q751660","lastrevid":49440607,"modified":"2026-01-07T04:04:56Z","type":"item","id":"Q751660","labels":{"en":{"language":"en","value":"On minimizing width in linear layouts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4177074"}},"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":"Q751660$B0E27B06-4996-4593-8802-2E97060090EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c7767f4d872768b98de0e49d89ede69787373e0f","datavalue":{"value":{"text":"On minimizing width in linear layouts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q751660$E243CC58-63F0-48FA-B142-EB9B3A36BC3F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7499d8100019121aa70d94fdb3da35563cad9810","datavalue":{"value":"0715.05012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751660$52511558-6095-4CE9-9468-65673C692680","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"904efa12052d66ef29c58c2aff32d2c6f4eb9112","datavalue":{"value":"10.1016/0166-218X(89)90016-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751660$48D4B52D-0C2A-4E02-8308-65BAA813872C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db380ca9fc70daf87380745a912bec378fa84e83","datavalue":{"value":{"entity-type":"item","numeric-id":751659,"id":"Q751659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$0A207430-2AEF-4B4E-B46F-69380A5ED706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"619555d96850b0d2a63f38f6976c99450dd5b2d1","datavalue":{"value":{"entity-type":"item","numeric-id":791315,"id":"Q791315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$3731019C-E8A5-4F19-A429-C21044316D49","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$338CFBE3-664A-4975-9F10-D6E886CECD17","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":"Q751660$24893F29-4CA3-41FA-B5C2-B8ACEA64DFBF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b67d206f884f4e3bc788f86e3accec2e74f48a33","datavalue":{"value":"The authors deal with finite undirected graphs with cutwidth 2 or 3. (Cutwidth cw is related to search number s and bandwidth B by: \\(CW\\leq \\lfloor \\deg (G)\\rfloor \\cdot B+1S\\leq CW\\leq \\lfloor \\deg (G)\\rfloor \\cdot (S-1)+1,\\) where deg(G) denote the maximal degree of any vertex of G.) Interesting corollary: for \\(\\deg (G)=3\\) the search number and cutwidth are identical. The author shows that these estimates are the best possible. Finally an algorithm operating for graphs with cutwidth 2 in linear time is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q751660$E4D4CE6F-ACA4-4527-89C1-07E6354F67AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"86c47e3aedde4615dd16421ee43ac00d4048a5ec","datavalue":{"value":"05B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751660$1DA45FF9-EB07-4B10-8EC0-48A834ED4F3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5cc0c47fb19ee72c034338ef83f6ed731f23343","datavalue":{"value":"4177074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751660$AF24886D-85C3-4C1F-8AF5-96F48100175C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b2ed3c130c30bac7174fa9b54a06645cc1227f","datavalue":{"value":"computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q751660$05EED960-079C-4136-B0D5-99E1C1C3B0C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789a5412a52c474b60446b45de1cf0e286aabe30","datavalue":{"value":"finite undirected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q751660$CD37BEF1-C5F6-4203-9754-947E82C304B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99fb8c69c202cd08d29b22488e32432b5a73c333","datavalue":{"value":"search number","type":"string"},"datatype":"string"},"type":"statement","id":"Q751660$A4AC85A4-6E1A-45D5-A285-8F887CB7D98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72494967642b9ea1b87091d53eb77ad552577f43","datavalue":{"value":"bandwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q751660$E83501D3-0F25-4659-9B1E-1692A27DC216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66e7957a80ee9b15bc3d1e2944fbb786e9926d58","datavalue":{"value":"cutwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q751660$6F7058EC-8989-416F-BC5A-F49D75A2E0D9","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":"Q751660$A8119E0A-BB4D-4122-8524-E03BECF48959","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb35434071b02cad61f63c7cadd55ff55ed5a42d","datavalue":{"value":{"entity-type":"item","numeric-id":3740255,"id":"Q3740255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$C7B574E8-9872-493C-991D-C6DDE40831F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93abefd43f60c4734d29bc653212ccc79b537d1c","datavalue":{"value":{"entity-type":"item","numeric-id":4165413,"id":"Q4165413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$54D14575-697D-4753-B88E-8B42557D70DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd01152085dc6c923faefae39879822e508a915","datavalue":{"value":{"entity-type":"item","numeric-id":3219762,"id":"Q3219762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$E8AC3C2F-16DA-4D7C-BFF9-D67AE3125831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73de5d06b50821afae240d17120a93d4c93bd6f1","datavalue":{"value":{"entity-type":"item","numeric-id":5286162,"id":"Q5286162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$2A06F77B-461D-4E2E-ACE9-A881442682E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b279fbd0caed565b76fad6f1a2cf4ed50d435368","datavalue":{"value":{"entity-type":"item","numeric-id":3951561,"id":"Q3951561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$F3E0898D-9855-4B89-ADF5-CC6800BEA83C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01ad9aadd446c6d5909b1353a38646e3156d4817","datavalue":{"value":{"entity-type":"item","numeric-id":3691781,"id":"Q3691781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$8F616D49-A67C-4AD5-9EDD-F72C8DDCDE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6873e217fa14d8d61b078525075498902f69fdce","datavalue":{"value":{"entity-type":"item","numeric-id":3777477,"id":"Q3777477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$4FD58E49-1F7D-43FF-B596-E151F0788C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9297d177cef3538cdee65914518573a4721a045d","datavalue":{"value":{"entity-type":"item","numeric-id":3050329,"id":"Q3050329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$23233839-F929-41A1-9F6F-288054649C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e235b1e856f674628ea45299d84fda7e204eaef1","datavalue":{"value":{"entity-type":"item","numeric-id":3208679,"id":"Q3208679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$382A52F6-F2F3-45F3-B0C0-43F6BBD1E45D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aec7a5195d839105a9eaed2e0df2aa8b7b1aebe","datavalue":{"value":{"entity-type":"item","numeric-id":4159394,"id":"Q4159394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$9FB229DD-29C1-4529-89B1-5F2F54AE3912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$97B98990-E0D4-442F-9C7C-9BE344AF5592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2479aa030f634bd795c8918a967327496f5092d5","datavalue":{"value":{"entity-type":"item","numeric-id":3771641,"id":"Q3771641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751660$1C9884D7-D148-40DE-85D1-CEE0531DAF72","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8afd0684139ca2e47776ed24b0b62a9426ff6010","datavalue":{"value":"Q128127009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751660$F65839EC-3268-4632-948C-771EA1239B2E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35f6527437b24afbca8d0d7c2cdcc1c391b1b0f","datavalue":{"value":{"entity-type":"item","numeric-id":3326858,"id":"Q3326858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d84223bea10d76c47dda56b82434802a6e254d7","datavalue":{"value":{"amount":"+0.8102662563323975","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":"Q751660$1A1AA4CE-5BA8-4F10-8763-62803220DBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fae9dc62bdf251351d2fafb4f9357434bc183476","datavalue":{"value":{"entity-type":"item","numeric-id":5462383,"id":"Q5462383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1a216f9b2a3497777d2d34d498acb629d85f349","datavalue":{"value":{"amount":"+0.8022077083587646","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":"Q751660$60871F4C-93C9-4729-A917-841CB131CD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d5306e33740637510a8adb0a52590b8a29b70b7","datavalue":{"value":{"entity-type":"item","numeric-id":5311524,"id":"Q5311524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3b3d567f8eb32cee52056ec5011c534b992e632","datavalue":{"value":{"amount":"+0.7951017022132874","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":"Q751660$6140374A-0712-4CC9-ADB7-9C633A742B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cc25eee3a230b84c862f96b936efe878dd7306c","datavalue":{"value":{"entity-type":"item","numeric-id":4796189,"id":"Q4796189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8c4f7c3d65c0c6cffd96f1d3d9f2e01272cec18","datavalue":{"value":{"amount":"+0.7770804762840271","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":"Q751660$FEAEE962-9C1B-4507-A772-F2F1EC53D5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a43a789a1df0e37ff42bbd136e4bf784d61a1a30","datavalue":{"value":{"entity-type":"item","numeric-id":4303902,"id":"Q4303902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2716990d57b50208a27261a99d83445872bd6b40","datavalue":{"value":{"amount":"+0.776733934879303","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":"Q751660$462E0ABD-260E-4BB9-9013-5325034AEA03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:751660","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:751660"}}}}}