{"entities":{"Q4846683":{"pageid":6876263,"ns":120,"title":"Item:Q4846683","lastrevid":47347282,"modified":"2026-01-01T11:23:02Z","type":"item","id":"Q4846683","labels":{"en":{"language":"en","value":"Problems remaining NP-complette for sparse or dense graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 790718"}},"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":"Q4846683$D04A2B09-5DBD-4BAE-BF51-E4926044E052","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2efbff020d47c3d3803344bd935fc66b32023d4a","datavalue":{"value":{"text":"Problems remaining NP-complette for sparse or dense graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4846683$6D2F5090-F051-4CB5-A3E0-A6148F819A63","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c07e4a26512eba11fc2cca4d7b964bc9723a682a","datavalue":{"value":"0829.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4846683$F0FE9D82-566A-4EDE-BC40-716D28CDC51B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"836368b6337657a52f201de441b98aececc2523a","datavalue":{"value":{"entity-type":"item","numeric-id":2725179,"id":"Q2725179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4846683$7AA6D9A9-ED14-45A2-BDAA-A4DE0BB1E295","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e989ac696f9909c5e911c306bf056166c7795429","datavalue":{"value":{"time":"+1995-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4846683$F5430191-19AC-4304-8DB5-CEB5A113AEA1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4846683$2CF2C1CC-E9B8-4398-A699-F9A69C0F1FC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4846683$94F1F3CD-3547-4172-BD92-2B1C6EEB0600","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8e1e21103ff44c7ef01d2985878e3670914f8f0","datavalue":{"value":"790718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4846683$0F696211-E424-414E-900D-0B5967D65496","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4846683$85E1E84E-FDE7-4A6B-8C97-19019B9AAAC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4846683$EFF9C170-A71B-41E8-9239-7AA69E93F485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q4846683$1BCA6003-BC3C-4E61-8642-9B9166068441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q4846683$D3417E1C-FD49-4EE6-B872-67362BE9D3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q4846683$4980B87A-012B-45A5-95CD-AEECB96CC9CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8492362146b232473140762e4eb450db7e5af4a5","datavalue":{"value":"Hamiltonian circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q4846683$3A231E21-208C-410F-A431-D87759EC3FE0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b09124aade2f9a2d1dad9d1d88ddbbb2bdabd00","datavalue":{"value":{"entity-type":"item","numeric-id":228794,"id":"Q228794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4846683$68F1DE3F-C5F4-4840-92D6-7DA97543AAE4","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":"Q4846683$6A65232A-7288-4BAC-8914-082C937F6C3A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f36a78bca2745168b16e8b44527ceb08b5e6eaf","datavalue":{"value":"https://doi.org/10.7151/dmgt.1004","type":"string"},"datatype":"url"},"type":"statement","id":"Q4846683$CD750D20-8692-4316-9789-FEB14CAA3337","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9bda79bbd929221423842083badd53e06a0e4129","datavalue":{"value":"W2054643041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4846683$7F72CC0B-A3BB-465A-BA59-A470E3B4D52C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6f8190fc06ddad77673b817631c48fee8eb6313f","datavalue":{"value":"10.7151/DMGT.1004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4846683$665CC497-BE7F-4452-8C5E-BBB654291D13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d5a121502f8950c75fb6bcfd273c7e34c7acc17","datavalue":{"value":{"entity-type":"item","numeric-id":1210313,"id":"Q1210313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07c9ff3ec70434c672925a60ff36292cfb49add5","datavalue":{"value":{"amount":"+0.7856037020683289","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":"Q4846683$DF98E7CB-B199-4C0E-B3B2-B0B47E4EB05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7a203e3d48628752ab581776b52cab67202d5b","datavalue":{"value":{"entity-type":"item","numeric-id":3325758,"id":"Q3325758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9341749e84ac13b58fe823601d488001d8f8918","datavalue":{"value":{"amount":"+0.7837050557136536","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":"Q4846683$0C4A7FDB-950F-4219-8948-D4157DCFA1D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"379f0719730f316d71685ac33928eb7ef6a7eff2","datavalue":{"value":{"entity-type":"item","numeric-id":629366,"id":"Q629366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d05cb72cd20a149a3f7358b20ba570618d3472e4","datavalue":{"value":{"amount":"+0.7767282128334045","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":"Q4846683$DD596240-68F1-4DB8-A87F-CC5BFB0B3AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05abe8b6575fbb9b943bc7bb21cb7649a0255938","datavalue":{"value":{"entity-type":"item","numeric-id":1262132,"id":"Q1262132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b34c84b0bf8b6b8c6a02acd3b94ee832c99ef32","datavalue":{"value":{"amount":"+0.7764426469802856","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":"Q4846683$B2685348-3F83-4DE4-8A72-505CB7FBD51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e891a6ef058d9598ea5f8d3af9e05231d8e29da5","datavalue":{"value":{"entity-type":"item","numeric-id":1331931,"id":"Q1331931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"954f426d47e589d324dfe9fa72d66c520de4b8a7","datavalue":{"value":{"amount":"+0.7697764039039612","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":"Q4846683$82641B20-6E2F-4D89-B4FA-7FE54B83A93A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4846683","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4846683"}}}}}