{"entities":{"Q1758876":{"pageid":1769618,"ns":120,"title":"Item:Q1758876","lastrevid":51598913,"modified":"2026-01-19T00:23:25Z","type":"item","id":"Q1758876","labels":{"en":{"language":"en","value":"Polynomial time computability of some graph parameters for superclasses of perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6108303"}},"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":"Q1758876$405C9566-74D8-4AE9-AD4D-A88D66852500","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd53f6752b90d0abf2d25f1262608c750ad4a823","datavalue":{"value":{"text":"Polynomial time computability of some graph parameters for superclasses of perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1758876$BF877C3D-208B-486F-9C9D-900663DCF4F4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a65b017d55fa22d9e2b0b01049dcc0097f76668","datavalue":{"value":"1264.05132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758876$88A5DC1E-6D11-405C-B861-947241053341","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"de0c489fa7595f830c98919bd998547e1a2ecb4d","datavalue":{"value":"10.1504/IJMOR.2012.046687","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758876$20562452-EC11-4665-BB6D-DCFFF183D6A1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"72a1d6eae62c5dc57677abd96ddd51da8ee6e751","datavalue":{"value":{"entity-type":"item","numeric-id":378132,"id":"Q378132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758876$CCFA594A-C9A5-4C30-B52A-927FDC927C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c037cd2f57be990495ee0f509d6fb5b2fddad9f1","datavalue":{"value":{"entity-type":"item","numeric-id":324733,"id":"Q324733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758876$DDD52ACE-21F4-4B59-B3AC-6D561FE527DD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"08904a7410b5f731fa63153720439160d216b374","datavalue":{"value":{"entity-type":"item","numeric-id":548461,"id":"Q548461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758876$11D63DEA-D0E0-497F-8427-2B7AD0575E67","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"16d9ed1da0749c54273c05a4ba5499c71e474aeb","datavalue":{"value":{"time":"+2012-11-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1758876$92C6BB11-A492-4E17-873E-7C4FDD7851F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"19c123dc0962a655a1452eb66f0a7bb79addab99","datavalue":{"value":"\\textit{X. Zhu} [J. Graph Theory 48, No. 3, 186--209 (2005; Zbl 1071.05037)] defined the circular chromatic number and the circular clique number of a graph and introduced circular-perfect graphs similar to perfect graphs. So far we do not have polynomial time algorithms computing these parameters, even if the inputs are restricted to circular perfect graphs. The authors restrict the inputs further to graphs \\(G=(V,E)\\) where \\(G[N(v)]\\) is perfect for every vertex \\(v \\in V\\), and use polyhedral arguments to obtain polynomial time algorithms computing weighted versions of the circular chromatic number and the circular clique number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758876$D1E1EE44-7BF2-44C9-8EB3-02370B14959B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758876$C4CE94BB-6E16-458C-9AE7-7CDED4B4C70D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758876$E6467FAE-655F-4B0A-AF68-F0F3BA2612F0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c415344c6cd78d511d99495b7332d02e5c64795","datavalue":{"value":"6108303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758876$2A240410-C59E-4FBC-A012-ED7E20D68CD9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50388f2c16d92154aa774284d257e30eaf1c6559","datavalue":{"value":"circular-perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758876$F2D90E78-1098-4CE2-902C-5A6250A4DEC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"756a92de806600ccd2ff23166271ffd1eef41605","datavalue":{"value":"polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758876$C71FD008-6F15-4BFC-8C80-010CB807E30D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ea75b11f76ebf3797d1166ff19b0fac44eb00d7","datavalue":{"value":"circular clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758876$14559B51-818D-4B9F-9CAA-0D5D4AFFF02F","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":"Q1758876$E4B6E4E5-76CA-497E-92D5-F3BC6A7D0F52","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8ed80755828417e2c68cb84dbcbeb745cc31d7c","datavalue":{"value":{"entity-type":"item","numeric-id":2840514,"id":"Q2840514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"723af6d5946022be9af77ba9ecfd590ad1b84a18","datavalue":{"value":{"amount":"+0.9397542476654052","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":"Q1758876$A452B816-6F04-40C9-9AB7-D577E2F1EB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fa80b4288023f43031130b1ca6dca6ca84501be","datavalue":{"value":{"entity-type":"item","numeric-id":378133,"id":"Q378133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cfb8e3ae88c9e0bf9892318c9959a73f8c46231","datavalue":{"value":{"amount":"+0.8847407698631287","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":"Q1758876$D1B8C49A-A789-4436-83E1-AF786136C41A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35147cc4b546bab5d88f86cc6f281208153d99ea","datavalue":{"value":{"entity-type":"item","numeric-id":2883567,"id":"Q2883567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78276da7071b3d8a4f1ddbbb6e7799f487233cf6","datavalue":{"value":{"amount":"+0.8537503480911255","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":"Q1758876$C6B7B28E-5681-4A4A-B639-DA857C18F47F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d5d87b2626da09da3b801692f39478549e044f8","datavalue":{"value":{"entity-type":"item","numeric-id":2509770,"id":"Q2509770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71797c79d2ca48673b2eb57ec67b86e49ddc4784","datavalue":{"value":{"amount":"+0.8045673370361328","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":"Q1758876$2CDCB76D-480B-49D2-BAB8-0793040ECCAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcbd576783500ef5b227a360a83572f901d3e7d9","datavalue":{"value":{"entity-type":"item","numeric-id":2857431,"id":"Q2857431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52c67159871cd70cfd228535827467bc7b1b1907","datavalue":{"value":{"amount":"+0.7990542650222778","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":"Q1758876$398448CB-3AEC-46E3-A73A-A02A02D8720E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1758876","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1758876"}}}}}