{"entities":{"Q794673":{"pageid":796521,"ns":120,"title":"Item:Q794673","lastrevid":48712315,"modified":"2026-01-05T16:50:02Z","type":"item","id":"Q794673","labels":{"en":{"language":"en","value":"NP-completeness of some problems of partitioning and covering in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3859172"}},"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":"Q794673$5EBB9004-8D0A-4A68-A77B-84ADBE37EEF6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba7c977e837109f53becc50d8e80978cb00c59b9","datavalue":{"value":{"text":"NP-completeness of some problems of partitioning and covering in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794673$9D74CC71-FC17-4B3D-8362-6C554BA4BFB5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ce100a4a1da7916d7b83421ab98b14b3d380f32","datavalue":{"value":"0541.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$A9D223A0-4F05-43E9-AFA8-807208170D2E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ded4d01ddfc308c5cfc35671998fbecd95ec5fa","datavalue":{"value":"10.1016/0166-218X(84)90101-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$CAC64027-6337-4B79-9846-577D08324E04","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":"Q794673$810C92E3-BBFA-4CC2-B6F1-F98917E186E9","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":"Q794673$E14B061A-1206-4D5D-954C-4756E9F90A7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac2b3757d602a0d14ec64bddfb84e3017120baae","datavalue":{"value":"The author proves that the following problems are NP-complete: 1) Given a non-symmetric digraph G such that \\(d^+(x)=d^-(x)=2\\) for all \\(x\\in V(G)\\), can A(X) be partitioned into two Hamilton circuits? 2) Given a digraph G such that \\(d^+(x)=d^-(x)=2\\) for all \\(x\\in V(G)\\), can A(X) be partitioned into two anti-directed Hamilton circuits? 3) Let G be a graph with maximum degree 4. Can E(G) be partitioned into two paths? Can E(G) be covered by two paths? 4) Let G be a digraph such that \\(d^+(x)\\leq 2\\) and \\(d^-(x)\\leq 2\\) for all \\(x\\in V(G)\\). Can A(X) be partitioned into two paths? Can A(X) be partitioned into two anti- directed paths? Can A(X) be covered by two paths?","type":"string"},"datatype":"string"},"type":"statement","id":"Q794673$E45D6CA1-B48E-44BB-97F7-2570988F9EDC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$9E050CF5-4AE0-465B-8958-912DCCEF3DFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$07663EC4-6302-4938-ACEF-B59BA7346B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$731950B6-3717-4D04-952F-99C18C34869A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$72CF3DBD-7AF2-499A-AAD3-CEB325A6BAD8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f501ddce00750e652b39a3936a9f735dc798479","datavalue":{"value":"3859172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794673$D2209C63-A961-415E-B399-CAD5659424B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q794673$1D3F1688-B8F4-489B-9F2D-14930BC4BC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74b82397d7c73e863f4eaef761403f4f99d3eef7","datavalue":{"value":"Hamilton decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q794673$4C97ECCA-F481-4B2E-A357-C5791A688F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56e7fca34c452381a57356a2418a828b70ad9fab","datavalue":{"value":"path decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q794673$E828E677-813C-47DC-93A7-41EF9F2B7FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48967f59fb173aabf410fae7f509b7c67a373bd6","datavalue":{"value":"path coverings","type":"string"},"datatype":"string"},"type":"statement","id":"Q794673$71BE4DEA-A01B-4BC5-9FDB-12A665812026","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9b0c064f917ec138c458b9bc909dd191fecab2a","datavalue":{"value":{"entity-type":"item","numeric-id":1322281,"id":"Q1322281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$C2204A41-ADCB-40B3-82D7-5ECECB103991","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":"Q794673$506C7B0A-2694-4D01-982D-29A5D2ACBD23","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":"Q794673$54318092-EB95-463C-B423-0746B31D1F0C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b78ca27225a1836f97985dd0f982aa2b70b872c","datavalue":{"value":{"entity-type":"item","numeric-id":5181723,"id":"Q5181723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$E96EE3FF-1CA1-4FF2-B99B-0852C0F82E50","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":"Q794673$7F08E2DB-B8DC-4D37-9228-A86B7E93C9B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b22ff16db5e764f439d43fdaaa3520cfd9262c75","datavalue":{"value":{"entity-type":"item","numeric-id":5181722,"id":"Q5181722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$EB8C3609-B953-4E36-B74D-01CE4A44947F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e3da11e15d84b8576d857908eb10029b44e01a9","datavalue":{"value":{"entity-type":"item","numeric-id":3870923,"id":"Q3870923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$B4FF8066-F325-4913-82E9-2806BCE9B85E","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":"Q794673$24459DB9-4AA3-488A-AD65-0F85259D3BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71a13ae72f67dcde4f82695a922dfb7c1481de3","datavalue":{"value":{"entity-type":"item","numeric-id":5632602,"id":"Q5632602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$4B17194E-46CA-4F46-AEDE-37320DDE3267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed128d9adc56c57bab4ec97ec0d9ae8364b5df62","datavalue":{"value":{"entity-type":"item","numeric-id":5670652,"id":"Q5670652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$92188575-88B1-4800-B6B7-341CF004AFD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9222cff0f604b36fc638a183fa48d7bb82199338","datavalue":{"value":{"entity-type":"item","numeric-id":3890725,"id":"Q3890725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$7BA98D18-ABC3-41D5-9AF9-982F44404089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6c66103cb7843c4cabbc833fee441340f275efb","datavalue":{"value":{"entity-type":"item","numeric-id":5628160,"id":"Q5628160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794673$9C75E591-7A06-459D-A3C2-83352A8873DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"297d155f1864a4589ce1d83b18f02997e4603422","datavalue":{"value":{"entity-type":"item","numeric-id":2465958,"id":"Q2465958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad992745cec6aa0067b35706ae2c3057eca91575","datavalue":{"value":{"amount":"+0.8225756883621216","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":"Q794673$348130AE-9224-4EE4-B63F-F87D8EDA51B4","rank":"normal"},{"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":"8aeaa8d66c08e8555028650ac4f65c95790e7b9e","datavalue":{"value":{"amount":"+0.8045974969863892","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":"Q794673$30FA6042-A648-4CAF-8123-F74FF16B36B1","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":"6f8e7814ed69df5e0e1bdeb59a8a62a3156d502b","datavalue":{"value":{"amount":"+0.8027042746543884","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":"Q794673$912D90AD-E492-42B2-A64F-4C454A59FF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f8d7ee34b974bc8121361c2a9a1ea811daddfd2","datavalue":{"value":{"entity-type":"item","numeric-id":1897369,"id":"Q1897369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df427d47089082db10f6b27f83b4339b98aae8db","datavalue":{"value":{"amount":"+0.7989810705184937","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":"Q794673$D78EA0FF-21B6-4B56-94B2-892C7A72525F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4107eee7ef35503f7bf4d605622a6e7b2613496","datavalue":{"value":{"entity-type":"item","numeric-id":5241609,"id":"Q5241609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0904598da3161268632882cc8fb0664e92ed6617","datavalue":{"value":{"amount":"+0.7979500889778137","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":"Q794673$380B6B11-729E-4554-A8FE-C4F42092DB15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794673","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794673"}}}}}