{"entities":{"Q1887072":{"pageid":1897814,"ns":120,"title":"Item:Q1887072","lastrevid":71064000,"modified":"2026-04-13T19:14:28Z","type":"item","id":"Q1887072","labels":{"en":{"language":"en","value":"The weighted independent domination problem is NP-complete for chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2118355"}},"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":"Q1887072$541D80EA-00DE-43AB-8791-FE5270F8B6D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"58d05eb3630ef7222ebcc66ba5d083e8fca4124a","datavalue":{"value":{"text":"The weighted independent domination problem is NP-complete for chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1887072$D0DB6E77-A955-414E-A188-1643ABC7C1C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d56086a9c9ea9503faf4236835f062f139033bb1","datavalue":{"value":"1053.05096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887072$5AF173BE-A21F-4FD5-80F7-7A344A33B986","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":"Q1887072$E9A72BA1-5861-4119-B819-0CF5AAB8CE7F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9270318d08aee06ff5ad0dd5710c08e39d64ffc","datavalue":{"value":{"time":"+2004-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1887072$BC4CEB5F-4F61-4321-9CD2-FB9F86191746","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887072$6145F189-DB58-4747-A1D0-420CA7749FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887072$38D2CC65-93E7-4D67-99A3-7BC6721566C7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"609e50f36a2de0f51e6f43f8ae8d1d35063076a7","datavalue":{"value":"2118355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887072$F3BE4C9D-DCD6-4AD2-8E61-E140E1F01B23","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87a6646fbe14acf0a8a3a5ed5b63f98f581aeebc","datavalue":{"value":"Chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887072$15693936-4E4A-49ED-B573-8FD9A60A4603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f29db8bc85f22ec25f4a2d96e8f1debf92812711","datavalue":{"value":"Independent domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887072$A771F708-4D98-4326-864A-E9FEDD672EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887072$F6569047-1390-4479-8A32-1CDEA7E3020F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"140be9d8f4e7723ad49789020190e03ad80ddfce","datavalue":{"value":"Weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887072$B37CEBCE-A0CE-4734-89D5-E9202B1F7F18","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887072$294B930C-1010-4792-8B85-EA5209B5A72B","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":"Q1887072$6C69D821-BE5F-4690-A3F0-6EEC13F30C7C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"51d3ef21ae42e5536aeaeded263ea358a2bd9f5f","datavalue":{"value":"https://doi.org/10.1016/j.dam.2003.05.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q1887072$7E9FE589-0333-4E59-8B86-79F2FAF4324D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cd0d3ab6bcddd69d78612cb62993ee7028088524","datavalue":{"value":"W2015322736","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887072$9F5257E9-00BD-4C46-A223-B7345B1D876F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"72505ced85f775300524892bdc5828b2de2211cd","datavalue":{"value":{"entity-type":"item","numeric-id":4247463,"id":"Q4247463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887072$8944A577-4299-4B78-A6E1-50F87F9CE450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcceaf2cce74b1109f08bcad4a414ce392831e83","datavalue":{"value":{"entity-type":"item","numeric-id":1382270,"id":"Q1382270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887072$FD95F7AA-B245-4017-9F85-E10CB52DB7C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aff4421d83319ba553decf5ffccebfa072fb3c1","datavalue":{"value":{"entity-type":"item","numeric-id":1169487,"id":"Q1169487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887072$A379CA0B-47AC-4FEC-A2E6-D5D641ECF00F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887072$11743213-E5B4-4F58-A91C-7ABE03FA8654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"785e7851fac401f47fc66697d0bfc439f0b289a0","datavalue":{"value":{"entity-type":"item","numeric-id":4368729,"id":"Q4368729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887072$36F31877-F570-41E5-B6E9-79B06F94858B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f48ee2c8f69a6b6c2009927f3c12627d43a5f22","datavalue":{"value":"10.1016/J.DAM.2003.05.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887072$E37BECC1-8635-4882-BC47-867FF7654978","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5ef8a14b4cbe5676928f0edc5965af87a167773","datavalue":{"value":{"entity-type":"item","numeric-id":2410364,"id":"Q2410364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad50edbcb3f00bba175e4c8747a77995a82ca91c","datavalue":{"value":{"amount":"+0.8672797083854675","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":"Q1887072$4597B400-FF0A-44C5-85C3-EDC01F0184B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97718e13d5629ffa677c319c6e637117b1f15b8a","datavalue":{"value":{"entity-type":"item","numeric-id":1687938,"id":"Q1687938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed144e886e02691fa82fe4f020c9d22111be4e2b","datavalue":{"value":{"amount":"+0.8493905663490295","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":"Q1887072$8CCE46A3-67CE-4A61-9963-13B4D43017C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d332efd11b5aa8726a4d1641c063fd63135e142c","datavalue":{"value":{"entity-type":"item","numeric-id":476836,"id":"Q476836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9995e548c8418da1b8292c13dcffd789a6ddcab3","datavalue":{"value":{"amount":"+0.8046975135803223","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":"Q1887072$9063D0A9-B8E4-49C0-9784-8DB8B0CC3C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a22846d64397afcfd70da668a4f4beefd4278cd","datavalue":{"value":{"entity-type":"item","numeric-id":2000566,"id":"Q2000566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d743a99b3dab216b4f3c2132a322bc62c23b4a68","datavalue":{"value":{"amount":"+0.8019228577613831","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":"Q1887072$2E745C27-0B74-4383-8269-DB8AD44DC257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7a98904b73ea7a1eaca6bd70e3f9cce161ef070","datavalue":{"value":{"entity-type":"item","numeric-id":6487953,"id":"Q6487953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11f1ed477e0f86ce34046d1679d32301989b271c","datavalue":{"value":{"amount":"+0.8017355799674988","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":"Q1887072$309511FA-BA60-4444-9BF9-BF35B42C050A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The weighted independent domination problem is NP-complete for chordal graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_weighted_independent_domination_problem_is_NP-complete_for_chordal_graphs"}}}}}