{"entities":{"Q760213":{"pageid":762062,"ns":120,"title":"Item:Q760213","lastrevid":48768181,"modified":"2026-01-05T19:53:34Z","type":"item","id":"Q760213","labels":{"en":{"language":"en","value":"Recognizing graphs with fixed interval number is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3883621"}},"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":"Q760213$78A675AD-06CF-45A6-9745-A3BA8AD1F4BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"957a10b03b8e6bf45230546eddee14c8cc74bd64","datavalue":{"value":{"text":"Recognizing graphs with fixed interval number is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760213$E530DE37-3464-4024-BFF1-6D5878F07329","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dccd1beb51bc1de91d4549fd9a47e4f774bf1e5f","datavalue":{"value":"0554.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$75030918-0ACA-4E20-99D9-09542DA65A62","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1c549580301b8eb3a3991a46f42a44c7acee03f0","datavalue":{"value":"10.1016/0166-218X(84)90127-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$2ABC2210-36CF-4B36-8210-714F77202F4B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$A929EE0F-893A-42F7-A799-6926551CD480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11c1f1f9079d02ebeb6b8cf94e1bc627bd0842c1","datavalue":{"value":{"entity-type":"item","numeric-id":304237,"id":"Q304237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$FCBFA765-780C-4B51-93C3-222EC880179E","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":"Q760213$B100CC2B-EA44-4736-95B8-C910B422D4AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q760213$73286A0C-0BDE-4AF4-987B-A36BE1D6413C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$CFA380DF-582A-4ECB-92BE-B86F38FEEF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$E6178F09-15CE-4912-ACDB-170AB54F94A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$8DC10B33-4CED-4001-A242-82BA771A347E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db35e1913cd98811de39b800dedb6cab7d01c2d2","datavalue":{"value":"3883621","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$55C59C81-BEC5-45FD-9559-214CCD2433D4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a949c568749d2f4337e1772be827516d5211abc","datavalue":{"value":"interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q760213$27915769-9ED0-4A25-8CFE-C6A3EA30BCFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q760213$7033B78D-EB53-4EB0-8AB3-AA2232AB9114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q760213$E077F38D-0782-4273-A452-D0535191FC37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f50cc51bed906b8146111e56b6c8c07790517771","datavalue":{"value":"interval representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q760213$7BB67E06-B417-4198-8911-4C29C3BFE8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cb62436c3d88f6714944eb3e4db3af39d3bc486","datavalue":{"value":"interval number","type":"string"},"datatype":"string"},"type":"statement","id":"Q760213$EBE78C68-BAE6-45C2-8673-5C9345C8BBD4","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":"Q760213$C19FCCEC-2D61-438B-B127-E77BC64DCBEB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$81C494C5-DCCA-4AF1-9775-F04116F6AFE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7d3dffde4b639a5080d558096cb7a34be71d72","datavalue":{"value":{"entity-type":"item","numeric-id":4146529,"id":"Q4146529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$8DF61109-97DE-4201-83CF-D00FC950873A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4931ab7df2ae059e9321582bbb6e0be5553d3815","datavalue":{"value":{"entity-type":"item","numeric-id":1145706,"id":"Q1145706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$6CC923DE-CF52-489B-862F-E8216D9C369D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f4df7ff86d27d228b9761e98fe15d8f8ac5c157","datavalue":{"value":{"entity-type":"item","numeric-id":3964599,"id":"Q3964599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$84DB4A4E-B42E-41A1-9DFD-7A861EDF4B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6c966d9e46b93ea8ea32d9adec138e8113d7f17","datavalue":{"value":{"entity-type":"item","numeric-id":3927276,"id":"Q3927276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$2F3B883C-FDAD-4C8F-91DB-FAFE6DFD3F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8f31457052bdaadc44ac0e5b4375c93c2acdf69","datavalue":{"value":{"entity-type":"item","numeric-id":792347,"id":"Q792347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$3E49C4B8-39C5-4101-A876-E8C2823F9F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"392a0b7409901f76701f37b973984e3fc9b16bb8","datavalue":{"value":{"entity-type":"item","numeric-id":4125734,"id":"Q4125734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$0BEF5FDA-0985-4BFC-BEE4-C07FA6E692D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44a562aa95e0a07278bdca02b49c4fe5b73f565d","datavalue":{"value":{"entity-type":"item","numeric-id":4144194,"id":"Q4144194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$2B199054-A431-4208-9994-86EEF238B2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47f7f006c2a4b394c2e5d5f20428d7148d181995","datavalue":{"value":{"entity-type":"item","numeric-id":786830,"id":"Q786830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$C7203CEB-47F8-4C40-AD16-497BEACFB8C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e24c073037298a747d5597bafa89654d8322d39","datavalue":{"value":{"entity-type":"item","numeric-id":3206997,"id":"Q3206997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760213$14E4C0B5-A642-4537-8F3D-B9B9C7AA57CC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5ee5faac354bafb2908f39441610f16ef925c66e","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90127-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q760213$DC0BEA71-A2CA-4FC7-BB09-848898418D0D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"922a8ec37552b68c7353079160ddd46268e85614","datavalue":{"value":"W2076027639","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760213$1DC53928-84B6-4246-88D5-9273EB58C326","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbffc9ecd1c65075bc7ce471a2103e06abd88530","datavalue":{"value":{"entity-type":"item","numeric-id":5962513,"id":"Q5962513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2fc72729143a8afeee44875e3ea5fc695a136a2","datavalue":{"value":{"amount":"+0.8178104758262634","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":"Q760213$5387D912-71AE-4968-99A0-7D6486209E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21b9ea48ba921d8a864a09d86a46a2fa28a39c9b","datavalue":{"value":{"entity-type":"item","numeric-id":4881297,"id":"Q4881297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfcad56a5c4c5f0bcc3507a1937986a8c9247427","datavalue":{"value":{"amount":"+0.8064668774604797","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":"Q760213$5355B8F1-4F47-4D30-9CC9-5CEBE238530C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02ca436ce9268fa9b4fd68991c9ffb8bd7428bed","datavalue":{"value":{"entity-type":"item","numeric-id":3587347,"id":"Q3587347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64fbd4acee567320b995df0643d895d6119615e7","datavalue":{"value":{"amount":"+0.8039085268974304","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":"Q760213$F5A9F3AD-27D5-40E2-B0DA-C6633A74B0AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c40f3a440684dbb9cf6fab766ada1e483fde5be3","datavalue":{"value":{"entity-type":"item","numeric-id":491160,"id":"Q491160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e68f1a9984ee547ea9a4f027ac877d1090c43d09","datavalue":{"value":{"amount":"+0.8028048872947693","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":"Q760213$A4A86D8E-18B6-4356-922F-F8CD5590A018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ab38539e2694654e319de9db0e859a3de4ae272","datavalue":{"value":{"entity-type":"item","numeric-id":4909568,"id":"Q4909568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6dbfe9711c70b6d5390aa153f2aab1f20c74f5f","datavalue":{"value":{"amount":"+0.8021570444107056","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":"Q760213$2D28968A-DB97-498C-8896-B70A6EAF146F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:760213","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:760213"}}}}}