{"entities":{"Q2768335":{"pageid":2779074,"ns":120,"title":"Item:Q2768335","lastrevid":47735077,"modified":"2026-01-02T13:49:35Z","type":"item","id":"Q2768335","labels":{"en":{"language":"en","value":"Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1699262"}},"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":"Q2768335$F838B38E-9B6D-4442-8397-827074D826D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6246ab0c170ed10ac25799c566b03667ebe6f6e3","datavalue":{"value":"0999.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768335$8BDBD705-54F9-4F11-94A3-ABB420D09ED9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"61f96647728e8d9cf38c91c3045ddf65bddf2136","datavalue":{"value":{"entity-type":"item","numeric-id":183294,"id":"Q183294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768335$B95E4716-0C6D-461F-9EBA-CBFEF97F1250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b985a74481e2ba1d54e1938dc2531093fd71e4ec","datavalue":{"value":{"entity-type":"item","numeric-id":266932,"id":"Q266932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768335$A358EFB0-3957-45AF-9BC3-CE0402C984AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c142bfdb3ba24d15560e9f10bd1352974c97a2c9","datavalue":{"value":{"time":"+2002-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2768335$0E77DDDD-07AC-4F6C-B18A-7EB9A73FE8FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768335$1ABD7269-7AFE-49CE-9FCA-E6E1801A9BF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768335$9E0E80D9-197F-46C3-AF00-89D6B484A3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768335$313EA723-0445-42B0-9CA1-6345BCFDF391","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ff675acdd1b16281fac8b7c85367ba7629012f7d","datavalue":{"value":"1699262","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768335$6279ADF8-D9B1-4589-9DE7-5F5EB9A336CB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768335$7708F3ED-82CB-4EBE-8DC7-FAEE1D537FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768335$DC98B1FC-A8AC-4449-9A14-72667E7996CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eb03826ecb9d862c3a8c13a3c8eb36c4bc27ecd","datavalue":{"value":"clique-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768335$590ECCE4-A92F-40FE-9FD8-C15D9DA49C4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768335$42B1BBAC-1B84-4DBF-9A21-5361D09BC51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768335$F005AECF-6BBC-4D55-8206-BD154028BB84","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":"Q2768335$09FCF7E4-6025-463A-9895-51DEDB2F3FF5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d9bc534de700a975ae446717736a90cfcbb33e43","datavalue":{"value":{"text":"Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2768335$30F8B046-B6BA-47FD-9AF7-9DF9F68A34EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"15890c6cf04f289b79234605e9ee932207839b30","datavalue":{"value":"The authors consider the following graph partitioning problems: dominating set, coloring and list-\\(q\\)-coloring with costs (fixed \\(q\\)), both from the viewpoint of the vertices and the edges. They show that all these problems (except edge-coloring) can be solved in polynomial time on graphs with clique-width bounded by some constant \\(k\\), if the \\(k\\)-expression of the input graph is given. In particular, they give the first polynomial algorithms for the chromatic number, edge-dominating set and list-\\(q\\)-coloring with costs on these classes of graphs. Unfortunately, the problem of recognizing and constructing the \\(k\\)-expressions of graphs with clique-width at most \\(k\\) is open except the case \\(k\\leq 3\\) which can be solved in time \\(O(n^2 m)\\).NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768335$51FD7B28-1B78-4687-B58F-6B208900E4BE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768335$F89CE55E-D120-442A-A96A-0BB58BB8C8D4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66a2d1e7e411ecff141fc8939e909f8a4de0a38c","datavalue":{"value":{"entity-type":"item","numeric-id":1861574,"id":"Q1861574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43fdab6923f0d3acfafb50de6e19cdbe25c90024","datavalue":{"value":{"amount":"+0.929912269115448","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":"Q2768335$853D5138-C2E2-4E8A-A701-D52541D0B7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75b8186ae99b4dc2f4c2ddee221494d31cd47cde","datavalue":{"value":{"entity-type":"item","numeric-id":1874418,"id":"Q1874418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2dbc028584c1b7e467bfc42bc3a5f9270029454","datavalue":{"value":{"amount":"+0.8836039900779724","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":"Q2768335$151AA786-9161-4DB6-AB3B-63722FAAC1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb96603e49e11e63d1e7c3446d0e75700abd6998","datavalue":{"value":{"entity-type":"item","numeric-id":884481,"id":"Q884481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"626e3f02a7dc707760353a9b2b637eafe552e7fc","datavalue":{"value":{"amount":"+0.8425273895263672","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":"Q2768335$C535FF6D-2C5A-410D-BE7A-5A8BCDAE6307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c82e8924548d5822346456297c9bebb9fc6be69","datavalue":{"value":{"entity-type":"item","numeric-id":4633895,"id":"Q4633895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58f2ddbfd0fc0f85a6ccb07803a1e1abb486a793","datavalue":{"value":{"amount":"+0.825652003288269","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":"Q2768335$0B63D11C-7A69-4489-A0CD-D4889F673A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d1cd453052eff0a5fa03dc183550e31d212e40","datavalue":{"value":{"entity-type":"item","numeric-id":5902536,"id":"Q5902536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"553b5b180e4758648527e0ecfb5cb9c696bfd5fd","datavalue":{"value":{"amount":"+0.8248961567878723","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":"Q2768335$942E0CA7-0534-4FE8-B298-97996D0FB89D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2768335","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2768335"}}}}}