{"entities":{"Q1108810":{"pageid":1119559,"ns":120,"title":"Item:Q1108810","lastrevid":49205584,"modified":"2026-01-06T18:35:59Z","type":"item","id":"Q1108810","labels":{"en":{"language":"en","value":"A polynomial characterization of some graph partitioning problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068323"}},"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":"Q1108810$36160B08-C057-4195-BC26-58965D0040D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5a16d8a5dfc4b8bcddc804fae5f2c159b408e521","datavalue":{"value":{"text":"A polynomial characterization of some graph partitioning problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108810$7972AAEF-E9FC-4AF3-891B-27406ECBDEDE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3195e2ddeac5c66c6291c21c697e35b336c1d322","datavalue":{"value":"0654.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108810$834BE9BD-F6FE-49D2-9993-982E5969762D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36870fc0ad75b50d752aa48b2a40f15c063aa9fe","datavalue":{"value":"10.1016/0020-0190(88)90144-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108810$C322C12C-B43A-4ECF-848A-6D2AD0BBC588","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"268c86183b2f5c73b7d063861a79c1303bb9cf99","datavalue":{"value":{"entity-type":"item","numeric-id":429691,"id":"Q429691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$28A23560-F3DA-4329-A95D-48BEDB0185A7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$DDDB5129-2400-40A0-BCE0-53B1ECD8A400","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":"Q1108810$5758CB76-CD16-443D-A3D9-33EE4EC0100A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b6ac3749e9ec41b4f77ab155a5fd2d31c0c7a01","datavalue":{"value":"The uniform partition (UP) and the simple max partition (SMP) problems are NP-complete graph partitioning problems, and polynomial-time algorithms are known for few classes of graphs only. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both problems in this class. When the instance space is extended to digraphs, a characterization is possible which leads to similar results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108810$C86CCD6B-61F4-4ED4-BFE0-927FE1B48021","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108810$EB733C4C-76B2-4E8E-BBA2-E9E755176E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108810$AD634299-D443-4C0F-BE32-F86881A067CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3f3beefb4d7b852a52c45806d95a4160c7eda64","datavalue":{"value":"4068323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108810$92AAF5C4-5244-48E4-ACB8-E4F89FD219A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108810$4EC18614-F5BA-4F18-ADE1-6DF234628799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e15fc25152589f056520453da57893ea9436bbea","datavalue":{"value":"line-graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108810$B7BA1BE3-26B4-4FED-831A-B3660BF5EDC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108810$378D0815-0795-4D39-B778-A07C9101E206","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":"Q1108810$4E831E87-A39C-487C-AD9A-1FC2AB56FED9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f7487ffa5a5ce12192c4f4c15c8721045fef29b1","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90144-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108810$44D8048C-992A-4E15-B9A1-C522715B7732","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a24c1e4ab67e294996dadd91a69529aa0903756d","datavalue":{"value":"W2044936198","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108810$50729DD2-6B3D-466A-81BC-59F824C53BE3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"175916359d5356dd13dd1efc4a7517f1e19ef4c3","datavalue":{"value":{"entity-type":"item","numeric-id":593988,"id":"Q593988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$DF2FE902-0102-48CE-950C-A23310EDBE35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871b0b619dcdcfea503ebb95e9e10caab2448bd3","datavalue":{"value":{"entity-type":"item","numeric-id":4726054,"id":"Q4726054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$A5BDCEE7-4CAF-4C20-AD41-C0D3F88C1D08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"418cd5ed6d6440cc0b5986bca4aa93f90ad28c0f","datavalue":{"value":{"entity-type":"item","numeric-id":5570136,"id":"Q5570136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$5DC37A2A-8E88-42F9-B61D-85215D0CA729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$8888BD17-A6B1-4EEA-BFFE-9767A0DC8397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ada15a34300791cfa9aaef8ea708f5f930686fb","datavalue":{"value":{"entity-type":"item","numeric-id":3951567,"id":"Q3951567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$D30242E9-0D87-485B-AA3E-3D8559CDE6B8","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":"Q1108810$1B810627-DEEB-4648-9017-44AC954253A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$24EB5C45-9132-4CDB-A712-6DDF2E825B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad0ccf7c915e555b736052d9a389d9d40d6ea980","datavalue":{"value":{"entity-type":"item","numeric-id":3315282,"id":"Q3315282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$01440D60-067C-413A-8E0D-54488A683357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$0A96F8B2-285D-46D0-8C80-A00D8474D8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$B709653C-ACC7-4382-A4B2-A2A3E657E7B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$4F2A0A0C-95E8-4BE1-97DB-0C7B90BF0F04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ad7df6fc66261f0adbf0d71d21cd6218acbb91","datavalue":{"value":{"entity-type":"item","numeric-id":4047571,"id":"Q4047571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108810$C40A574A-547A-4029-BF47-B6B759DC0DA7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14eff9d380f039b0b4b904c5736a78b972e4455","datavalue":{"value":{"entity-type":"item","numeric-id":3835330,"id":"Q3835330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"337e56a117d465df8eca0d79a7da26c0b3ffb891","datavalue":{"value":{"amount":"+0.9239468574523926","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":"Q1108810$C76C3921-3CDE-4D8F-AB65-F754D6406D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04d436114d056d15172d896276dc0de16310669","datavalue":{"value":{"entity-type":"item","numeric-id":1283792,"id":"Q1283792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1af8774fce9db12928be08ea98787ce8615fa146","datavalue":{"value":{"amount":"+0.7970690727233887","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":"Q1108810$3E959897-08CD-4461-AE98-D95D8EBCFB6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a655a699c11e13f2eafcf9fce43157f3d2a437e6","datavalue":{"value":{"entity-type":"item","numeric-id":2366610,"id":"Q2366610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ad87f752969037dd983445a04f90642ccb701ca","datavalue":{"value":{"amount":"+0.7940195202827454","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":"Q1108810$EF7A20C8-CCF4-439A-AC05-ED44B80109E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b16688039f293f5ab25affaea296599de4bdf88","datavalue":{"value":{"entity-type":"item","numeric-id":3736913,"id":"Q3736913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f509e9e1235fc0971f8b3ad451ad11cb8de8b448","datavalue":{"value":{"amount":"+0.7897728085517883","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":"Q1108810$B604D1AC-F190-43FA-B103-24753A9C6409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6996a03be716670f505d0944bdf401eeed72fcb2","datavalue":{"value":{"entity-type":"item","numeric-id":672380,"id":"Q672380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb8174eb7446c3d925654e1ae68565cfc9e592d7","datavalue":{"value":{"amount":"+0.7841023802757263","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":"Q1108810$065AED5A-AC36-411B-AC2D-B0F6E80AAE41","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1108810","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1108810"}}}}}