{"entities":{"Q1363736":{"pageid":1374475,"ns":120,"title":"Item:Q1363736","lastrevid":46485561,"modified":"2025-12-24T21:42:32Z","type":"item","id":"Q1363736","labels":{"en":{"language":"en","value":"A nice class for the vertex packing problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1047163"}},"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":"Q1363736$79E83BB9-41D5-4ADF-827E-27AFF446B26C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cbc5d4ca24c2eec2bc529db8a24317303a4e1527","datavalue":{"value":{"text":"A nice class for the vertex packing problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1363736$720808F7-2082-4AEB-A055-6877B04F6BD0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"65a868eb0baeba41ccbcf469db8ce68bbaeb3e97","datavalue":{"value":"0879.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363736$6A20C702-3326-4373-907E-F1DE56D64958","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"396a51f9c1bf6aaccffa73c28dbcdee18059a609","datavalue":{"value":"10.1016/S0166-218X(96)00114-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363736$D2664B2C-3E4A-49FA-92DE-0FCFB207D290","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd94e4e7f27f948a7315c2ac01ba439ef6354378","datavalue":{"value":{"entity-type":"item","numeric-id":235657,"id":"Q235657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$C86232C2-4BF8-4503-BFFF-DCC5ED400BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"04e71569b0ebdef8629fef55e83176d19ee5910a","datavalue":{"value":{"entity-type":"item","numeric-id":849136,"id":"Q849136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$05B951C3-17C6-4F49-A95C-92FEB3EC80AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"42b3be3fd84ab4e46e98f17275cc4a0c654521b5","datavalue":{"value":{"entity-type":"item","numeric-id":185365,"id":"Q185365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$D4556D24-968A-44DE-B102-10BB6B7859A5","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":"Q1363736$071C82A4-B5FA-416D-AFC1-B621AC0131C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"17450649df8fda814560fb6476ed41552e57c61b","datavalue":{"value":{"time":"+1997-12-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1363736$9D7871E9-026A-4DC1-A59A-E795A28FBE60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1363736$BDFD6323-A554-4085-8C66-04FDBC69ADC2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6dd57efd616636b25ee4bde3690e8e259f0a8080","datavalue":{"value":"If \\(v\\) is a vertex of a graph \\(G_2\\), we can substitute a graph \\(G_1\\) for \\(v\\) by taking the vertex-disjoint union of \\(G_1\\) and \\(G_2-v\\), and adding an edge between every vertex of \\(G_1\\) and every vertex of \\(G_2-v\\) that was adjacent to \\(v\\). If \\({\\mathcal C}\\) is a class of graphs, let \\({\\mathcal C}^*\\) denote the smallest class of graphs containing \\({\\mathcal C}\\) and closed under substitution. The authors call a class \\({\\mathcal C}\\) of graphs nice if membership in the class can be certified in polynomial time. If \\({\\mathcal C}\\) is a nice class of graphs and \\(G\\) is an arbitrary graph, consider the question `Does \\(G\\) belong to \\({\\mathcal C}^*\\)?' The authors show that the preceding question can be answered in polynomial time whenever a forbidden subgraph characterization of \\({\\mathcal C}^*\\) is known. The authors provide a forbidden subgraph characterization for \\({\\mathcal C}^*\\) when \\({\\mathcal C}\\) is the class of graphs that are claw-free or bipartite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363736$5C76E50E-8BA4-488F-A7D2-8AB80C1EA215","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363736$9CAAE908-8D39-4932-B3C2-1F1FE34CAD4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363736$E7A5337B-71AD-4742-AE25-049EF8CAC528","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a3fc706e3dc55c3ab1f0ca8d8b69f503c0a9435","datavalue":{"value":"1047163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363736$FE65CD42-F54C-4E5F-B005-191572C66AA5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d63791b0c45f397660397defe58d8678aeee633b","datavalue":{"value":"Homogeneous sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363736$38CE299F-E702-4AB1-91C2-C6CE6B9DAD6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"765ab1d5379755eb3e4e5d30a0f6d93a0512b558","datavalue":{"value":"substitution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363736$08FE463B-A3D2-4C0F-A15D-9BF9344485B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ac3d4aa0b6147605e0d11fde19d86ae13070cd6","datavalue":{"value":"vertex packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363736$E0DF0AC6-F0B3-46D6-AF0D-A3CAD7165B51","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"18d5150f70f677eb92738e1c6793c1fd0d1cb2c3","datavalue":{"value":{"entity-type":"item","numeric-id":210144,"id":"Q210144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$15AB332C-E73B-466A-A9E9-506E8D66D1B4","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":"Q1363736$14776360-0BAA-4969-A13B-0288EB15C7E8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"246e997ac5be85679ca39a610c5e7ac50170cbb8","datavalue":{"value":{"entity-type":"item","numeric-id":675293,"id":"Q675293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$AE63F38B-51B0-41EE-80D3-6E0ADAB49483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$DD25289D-D58A-4260-B7E0-C3151B1B944E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$6E22AB3A-4534-495E-9EE6-E3F5DF425E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f80bd66875089f385bc846e7e7f8ca82fdf2a5","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$FA8B5942-7D18-41AA-B260-C7686533B0F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed91ed0176924a73cbecba9388f8a04535563e10","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$D6563145-ABA0-449E-A531-F20ABB77F0A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6158b50eeb07f11af0caa758cb3e8ea0fab5c43e","datavalue":{"value":{"entity-type":"item","numeric-id":2366214,"id":"Q2366214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$5008767B-FF27-47A1-B8CF-1DC5EC89FDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$69A82A6C-C068-44D1-B54F-52424AE5D2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$AC40C8DB-8DFF-421B-B196-E0A847C1D8A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7af979d76b1c20fe92fb0191ce684d26e85c0463","datavalue":{"value":{"entity-type":"item","numeric-id":4167596,"id":"Q4167596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$95FD9C0D-8DF7-4855-9A59-0511D2A3E27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$CE36E829-F177-458E-A378-26D345B249D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97ca141c898326cfe034e4da2d173763055f4264","datavalue":{"value":{"entity-type":"item","numeric-id":3128916,"id":"Q3128916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$3FB1E074-DE67-4587-8498-668E80838F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$F3C17ACE-98B4-439E-A470-2A42BA7C136A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ccf2ce6ffe932287a3e8f6d3b281b44fd4ad0eb","datavalue":{"value":{"entity-type":"item","numeric-id":4770411,"id":"Q4770411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$46B01A6C-7033-4359-8011-B31A1B683BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363736$8EACC35C-D75C-4045-A02C-EE8C201FB8A4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2a9910c6ae37111776aded9d2f9cba24ec7b2746","datavalue":{"value":"W1986815960","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363736$AF0B352E-ABD9-48D5-951C-5C3D89E478F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e855218ce6ba6d44aa4e557e50b2786a09c56822","datavalue":{"value":{"entity-type":"item","numeric-id":2366214,"id":"Q2366214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0903cddf163727bdcc7c863c68fac8f665d0dd42","datavalue":{"value":{"amount":"+0.8182024955749512","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":"Q1363736$29567B42-AC12-4DE6-8B99-08A25D48D675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0a9af183b96fe91adaab690ba91524d01599e7a","datavalue":{"value":{"entity-type":"item","numeric-id":1811128,"id":"Q1811128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"900c68414d2134fa879bcea78c3cd9e83d1768b5","datavalue":{"value":{"amount":"+0.7716397643089294","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":"Q1363736$67981408-EAA9-4EFD-90EF-428D17E770A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e1d2df1fccf8469543cd597c05d45fa970dd75b","datavalue":{"value":{"entity-type":"item","numeric-id":1779506,"id":"Q1779506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23da1d19ec790e20c8d3068bd27f60cebb5cfca6","datavalue":{"value":{"amount":"+0.7510589361190796","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":"Q1363736$B7ECF0D6-E8AC-41DA-9237-926EEE65BA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09a947e245e7b295cdcdd14a68c702062d2b84d7","datavalue":{"value":{"entity-type":"item","numeric-id":1068852,"id":"Q1068852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d87004f9c86e24ae65145668fa0035c812954356","datavalue":{"value":{"amount":"+0.7463937997817993","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":"Q1363736$86B8BB7D-E188-4EA4-A96D-AA3557F4CF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aefe9fa477b124d5ab7e09cf38fadf1a1db4357d","datavalue":{"value":{"entity-type":"item","numeric-id":1377871,"id":"Q1377871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fcf5bdbff064d6489399cea627dac459d6715d8","datavalue":{"value":{"amount":"+0.7437024712562561","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":"Q1363736$251455A8-D1C9-444A-B343-6BE71EA746E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1363736","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1363736"}}}}}