{"entities":{"Q995581":{"pageid":997429,"ns":120,"title":"Item:Q995581","lastrevid":50156558,"modified":"2026-01-13T07:16:53Z","type":"item","id":"Q995581","labels":{"en":{"language":"en","value":"NP-completeness results for some problems on subclasses of bipartite and chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5186620"}},"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":"Q995581$B6C48F9A-4531-47DD-B72B-933BC3DA0FA8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91c3f7926bf59b06d561fe6dc24715329b04dbc2","datavalue":{"value":{"text":"NP-completeness results for some problems on subclasses of bipartite and chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q995581$AC84D4E7-325B-45C7-A2B5-7C310F65DC8C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e896a5f50e5b1da3a618f925123902f9912ffa3f","datavalue":{"value":"1188.68208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995581$FE93063C-0710-4DF6-9B04-45BCD302D624","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad5c5d371ac23870f99f4ac9184774af1d36f4a1","datavalue":{"value":{"entity-type":"item","numeric-id":868039,"id":"Q868039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$FAD27444-BE19-49D2-82BF-66816D05FE06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6269fca4b2624f5addc49e1e2be512d43e29d093","datavalue":{"value":{"entity-type":"item","numeric-id":294752,"id":"Q294752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$15A92F26-F867-4C3B-9419-27BC2FF56530","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$586838C3-2DCE-40E2-BB1D-E7DEC0E71FF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d4ccb5809271d2f0bf96f65b85084aa847fe92ef","datavalue":{"value":{"time":"+2007-09-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q995581$B9CB40BF-2949-493A-908E-9D2668F3CA90","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995581$DBE408E6-15F8-4D95-8008-62064DC9CA4B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91b571673c4e837f267f9a441c26557289236ed6","datavalue":{"value":"5186620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995581$B2686C28-0129-4C63-A743-AD18AFDDC40B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba198390cf59b2be826ef940c3844dc44ac9cdf8","datavalue":{"value":"harmonious coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$3DE933A9-6233-484F-8C75-87CD782DEFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ad672147a02bdd9cfa0d54fdd1709b7d97bb8ba","datavalue":{"value":"pair-complete coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$605ED468-D030-4B58-B0D3-09D6BBBC2A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5603eddd430a6960149af3e6ebd8667d6ec51a0e","datavalue":{"value":"\\(k\\)-path partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$D04D1F49-3A79-478E-B61D-A804D2D5CC1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d752149583d7ee9659fd619df8f643680fb8b09","datavalue":{"value":"bipartite permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$396ECF81-7F8E-44C8-8C90-624254CE4D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d105f72a0dca8565633f37a97c549da31fb85824","datavalue":{"value":"convex graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$7CDA824D-D4AA-4986-B93A-D403C37A2605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e54228e451ca302f53791967760861bf8da38635","datavalue":{"value":"quasi-threshold graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$969D585B-B5E1-4761-A108-477BC971D0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89c7b74075c02a9f90535ca1118f6218f248cc31","datavalue":{"value":"threshold graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$C8466BF5-2E8E-4258-9BC6-6F89DABA32D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q995581$6EBEF9E3-9397-4F7D-A2CA-7B3FFF41A8B9","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":"Q995581$BA447252-AA8B-4415-95FE-6CBAE1822B3B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5a85b732120aaa406e52d7b05ac7953f0b83529d","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2007.05.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q995581$F4D0C5B5-D1BE-4B35-9020-853ADCA6C307","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"542e6b1693031e79c5736ccadd7bf356a5d46cf0","datavalue":{"value":"W2007549941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995581$E9CBD8ED-5776-4D90-9517-09113B0AD306","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d6fea3ece14e78efe08d34891e1188ca78ad2ca","datavalue":{"value":{"entity-type":"item","numeric-id":2457020,"id":"Q2457020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$3CA9EE38-5C82-466E-AA9E-3B8CAC67FC92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$9870AF70-D25F-4B6C-9DC6-6170A2F9E13D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac7f04bfc755103b505310e94b46f9d83558eff1","datavalue":{"value":{"entity-type":"item","numeric-id":1825646,"id":"Q1825646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$7E41E761-24A9-45B8-865D-347F2BA24730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3628f1effd0c1124025a6bdbd498396fd56263e","datavalue":{"value":{"entity-type":"item","numeric-id":4364806,"id":"Q4364806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$1DCF32BC-4A32-45F5-AC39-9DFEE320191A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$00E97ED2-EF89-4B06-BA10-848AC24AA1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"248f1a6f17dd2ddee62d060f2cd13eeda44b18e8","datavalue":{"value":{"entity-type":"item","numeric-id":4352945,"id":"Q4352945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$332E63F8-0CC9-4D00-AA2E-153F4B9DCEC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b670eda2d4d1ed2bb9199c53c7aa9dd094d489f5","datavalue":{"value":{"entity-type":"item","numeric-id":1346692,"id":"Q1346692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$38271C9A-68A1-4100-9EE0-CE0F319BCD11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2195fcf50c30bfb3d44ec94fc1feab3ae8df026e","datavalue":{"value":{"entity-type":"item","numeric-id":1065819,"id":"Q1065819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$305A949A-5487-4F52-AF8A-5D5BA0D61E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f49b59a3415def5131877943b20d9ec0d84493","datavalue":{"value":{"entity-type":"item","numeric-id":4740588,"id":"Q4740588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$C5A991F9-C0FB-4372-9C74-4A00B89B24AD","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":"Q995581$D94DAA98-D710-49AE-B29D-D674A15DFBB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$24B73ED4-0593-4D99-A90E-05D05EC28FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dff1b6998120ff9e6ad67c6efd96c489b7dbac09","datavalue":{"value":{"entity-type":"item","numeric-id":5591379,"id":"Q5591379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$26B51787-0624-47D1-8C3E-8D04DD41FE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4327677991eb2845cc8d90a47d7438e36ce2734","datavalue":{"value":{"entity-type":"item","numeric-id":5578801,"id":"Q5578801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$CDF4D056-A054-4585-A91A-507942153BC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb29af076423b8bae84f5021e85f7864f0c71bd2","datavalue":{"value":{"entity-type":"item","numeric-id":3331240,"id":"Q3331240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$99AD6E33-F231-45E2-A2D0-786D9D4F2155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17f12332ca89ec48bfc3d5560520efcbd09cf4","datavalue":{"value":{"entity-type":"item","numeric-id":1145508,"id":"Q1145508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$FA8F9865-FD94-4717-BACD-3F7CBFD91CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c86c1263fddb9e474b3da90f7c5318f889babac3","datavalue":{"value":{"entity-type":"item","numeric-id":3203054,"id":"Q3203054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$05EAB139-5FCD-4804-A8FC-1E842BB3F085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce692d0cb3171b3212344fed76f4b1b7b45c6c9f","datavalue":{"value":{"entity-type":"item","numeric-id":1327235,"id":"Q1327235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$BADD11E5-A1F3-41EE-A382-E0C7E35EBFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58432d9641eaa0d90e7d7119252822fbee0d5d99","datavalue":{"value":{"entity-type":"item","numeric-id":1878696,"id":"Q1878696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$8A850954-8EE0-49B8-BB2B-11651F76FD38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c574697d65aafc142f8fc6d4d01e783c6f077e04","datavalue":{"value":{"entity-type":"item","numeric-id":294753,"id":"Q294753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$69007EF6-466C-4E33-BE11-10F5B89FD4AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da2d95ac31a70052a778a9e28ab2a7a081f20922","datavalue":{"value":{"entity-type":"item","numeric-id":1092931,"id":"Q1092931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$FD20F93E-31F0-499D-9AF6-F3E153FB386A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b33c5f43d87fa6332659e6015e68c4c47916ede","datavalue":{"value":{"entity-type":"item","numeric-id":1401225,"id":"Q1401225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$62450DBC-C540-48AA-8F38-C15710560533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f75e963e4698fc5b7765322c8dcd3f97c2f3f671","datavalue":{"value":{"entity-type":"item","numeric-id":2716628,"id":"Q2716628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$2C7C7FB9-8F92-4549-9333-178A0D20B1DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42fdf6613d659593a8db2839e42759447a07ea69","datavalue":{"value":{"entity-type":"item","numeric-id":1377668,"id":"Q1377668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$76142972-75A8-4D92-BD40-8C9D6089726B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7032db704a3c4fcea69481a5580e82a7d02eda","datavalue":{"value":{"entity-type":"item","numeric-id":3903038,"id":"Q3903038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995581$AA862A2E-00D9-487D-9DD3-361DA2B08A80","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"60ebe59465fc535e0edc98fb2f83ce07368c7ed8","datavalue":{"value":"10.1016/J.TCS.2007.05.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995581$58190907-05C8-4669-A549-6DB52E5BC966","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b6f00a04ac5bedc83bfc8ad1a57d278daefe0e9","datavalue":{"value":{"entity-type":"item","numeric-id":2457020,"id":"Q2457020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8e6ef00ea51aaa556c68a278236fcdecbef9f6e","datavalue":{"value":{"amount":"+0.838901698589325","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":"Q995581$B96809AA-A100-4711-9FE9-3C113046485A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc197472ac81b82d27c200f530cca30a7bf6a88","datavalue":{"value":{"entity-type":"item","numeric-id":1401225,"id":"Q1401225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"381e621be980ed54f8756d51100de94c272205d3","datavalue":{"value":{"amount":"+0.8351778388023376","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":"Q995581$87FBAC11-6805-4DF2-9B44-E6A2BA847C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6417d414c8af2ee34f4ef38f3b618cdc3608382a","datavalue":{"value":{"entity-type":"item","numeric-id":1099628,"id":"Q1099628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"063488550f5a74f809ccd004ceeecd6d7960be78","datavalue":{"value":{"amount":"+0.8045704364776611","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":"Q995581$A7D156B7-4A32-4ECD-B3BE-8DBACABE2187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de39341baeacf0550e5c5b6efde3790d5a2f6030","datavalue":{"value":{"entity-type":"item","numeric-id":2716628,"id":"Q2716628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cd576f7767109025d681396050ae1d0c458fc3b","datavalue":{"value":{"amount":"+0.8026497960090637","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":"Q995581$4C9BBA30-F30D-4EF5-92AF-45FD5F854E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9683a7b50fac958bf57451d45633d3fb8757dce4","datavalue":{"value":{"entity-type":"item","numeric-id":3679238,"id":"Q3679238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f10bdd096217cf56732a35ae2537b5980a40d81","datavalue":{"value":{"amount":"+0.8023894429206848","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":"Q995581$AC6227FA-0E8D-43BA-AA0C-DCD4CF2F5362","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:995581","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:995581"}}}}}