{"entities":{"Q2494439":{"pageid":2505182,"ns":120,"title":"Item:Q2494439","lastrevid":49865140,"modified":"2026-01-11T10:30:04Z","type":"item","id":"Q2494439","labels":{"en":{"language":"en","value":"Recognizing Berge graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5036259"}},"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":"Q2494439$0002C810-BDBA-4A71-A536-EFB142B5C898","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae9fbdfbaeed9df9587bfc50647ff49de0f89aeb","datavalue":{"value":{"text":"Recognizing Berge graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2494439$C52DAD43-7C69-49F6-B1CB-56EE979B7950","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f0e3c6df9a4dbb2d03139c3338bb080d6ccc7282","datavalue":{"value":"1089.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$3590658C-A656-472C-BAE3-ED06858C02F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$696F6387-F912-4563-81BC-DC7E42EF3FE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0492ebd1f79ca17bbf885d93138b7076f265fb56","datavalue":{"value":{"entity-type":"item","numeric-id":2192480,"id":"Q2192480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$5E10F723-91EE-463C-A564-B75016BE04F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"49d526c3d79304181fc7ca4f0d651cb2855460b7","datavalue":{"value":{"entity-type":"item","numeric-id":203962,"id":"Q203962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$C4E4A6E2-3279-4F5D-B556-D38D55912B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$163B5644-1694-4C92-94BF-D989B6F5DE62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$0EB62FB6-7541-47BC-9CFF-63C160DEF8B1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$2398ED45-49BF-45DB-99DC-A2E5616D011D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2100ced5bb0fc7a2f2d75de03e2412195897a08","datavalue":{"value":{"time":"+2006-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2494439$FF383EF9-C779-43FC-99B4-CC26DC996B99","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92ed58549826c39f10015efd27a19ccd23c2e50e","datavalue":{"value":"A graph \\(G\\) is Berge if no induced subgraph of \\(G\\) and its complement \\(\\overline{G}\\) is an odd cycle of length at least five. It has been an open question whether testing Bergeness of a graph belongs to NP. In the present paper the authors give an algorithm for testing Bergeness with running time \\(O(|V(G)|^9)\\). It makes use of a ``cleaning'' technique which generates polynomially many subsets such that one is a near-cleaner for a shortest odd hole.  The algorithm given here is independent of the proof of Berge's strong graph conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494439$6F43FBA5-A4D7-4AEB-AC4D-91504AAD14D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$1C160BEF-380F-4B49-B919-799E3018F135","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6f295b90b2b88ac7e08e9334a298650e3f907e59","datavalue":{"value":"5036259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$E91BEF1B-3899-4F21-9078-4809D919A69C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494439$AF165573-6F56-4CF8-A4DB-EAA2F18D19C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494439$99E3471C-3330-4751-98BF-CC207E6BE5E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b43d93c54208b4df892f772f1b5ec06753d1b280","datavalue":{"value":"strong graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494439$1C3B4FB2-16D9-43F2-BA57-334C101FADE1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"44ac6379211a77698a770218846f04345ca2854f","datavalue":{"value":"Q56388170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$F8C073C8-20D1-4CF1-B22B-5CB79F99241F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82f32c91e1eb0067a512f27a8cb077a4f29f958","datavalue":{"value":{"entity-type":"item","numeric-id":640843,"id":"Q640843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494439$D58510AD-2539-40B5-8DA8-B8A5AF7580E4","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":"Q2494439$7F45003A-3E28-49EA-9145-FE3135574E5E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"515ab5c41df80e66c2426d82209dd3fe67092875","datavalue":{"value":"https://doi.org/10.1007/s00493-005-0012-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2494439$3745426D-7107-4BFC-B7D7-231DE7C14B68","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8eaec5daca34abd1e5058a185f2fd5cd9056db04","datavalue":{"value":"W1991728994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$F39C5598-9F30-4DB1-B295-E68731DB49AE","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"77ca86c29b674d63ac8b26b623509d48cf85879b","datavalue":{"value":"journals/combinatorica/ChudnovskyCLSV05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$C6342748-3455-4D45-8E2E-4EBA681F06E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"012f5198b07e5f39c4540f7518e05e9345d14191","datavalue":{"value":"10.1007/S00493-005-0012-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494439$B1D248D4-B67A-4EF6-A979-5EE20A97242E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74a5efd0ade566877d97b34c730ed966580db288","datavalue":{"value":{"entity-type":"item","numeric-id":5487777,"id":"Q5487777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"160fb6e909505e37c0403c0f6387027167d557cc","datavalue":{"value":{"amount":"+0.7915638089179993","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":"Q2494439$843CDD74-6FA0-4129-95CA-1A8D16436DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4961851ce6a3c260bb9da312fb38c3e7d7012cfe","datavalue":{"value":{"entity-type":"item","numeric-id":2464161,"id":"Q2464161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cee6c835fc12fd81654724fc422cea270cdb53a8","datavalue":{"value":{"amount":"+0.7874172925949097","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":"Q2494439$DE7F75AE-743F-47AE-945D-7006C415B9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706646c5ec7624ff64c7e5e38d9fa854ab6fb321","datavalue":{"value":{"entity-type":"item","numeric-id":3149869,"id":"Q3149869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88bfdb1f19cc7e3bc30237462876e190b621358d","datavalue":{"value":{"amount":"+0.7860019207000732","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":"Q2494439$16E72A0D-570E-4B2B-92C7-C365C433A9E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"330cbdb2c3c7f93aca2061a308ef7f78cdf2a21a","datavalue":{"value":{"entity-type":"item","numeric-id":3487429,"id":"Q3487429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88bfdb1f19cc7e3bc30237462876e190b621358d","datavalue":{"value":{"amount":"+0.7860019207000732","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":"Q2494439$82EF0213-BB88-45F7-AA9B-5FFD1EF66F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9299e61b39baf41c3a790876986f28d5c9440667","datavalue":{"value":{"entity-type":"item","numeric-id":1719576,"id":"Q1719576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71f2aee3a201205ab07746d2a2984f9dd6b3f481","datavalue":{"value":{"amount":"+0.7841669321060181","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":"Q2494439$3650CA34-5FA4-4FD0-9F57-78F31EC957D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2494439","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2494439"}}}}}