{"entities":{"Q1893154":{"pageid":1903896,"ns":120,"title":"Item:Q1893154","lastrevid":71087310,"modified":"2026-04-13T19:23:49Z","type":"item","id":"Q1893154","labels":{"en":{"language":"en","value":"The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 769292"}},"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":"Q1893154$0B788036-1733-4D09-8D69-2E78DB8D83EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac1d57a6ce7b9d3cb56edfb6cf49808c0bd5e028","datavalue":{"value":{"text":"The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1893154$B686A30B-2FC5-46A0-976A-C586650DEF05","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c6dbaa0a2182e7f8945e1b68728eb29f3d1c8286","datavalue":{"value":"0823.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$A5CB96B6-F8C5-40A8-ABE8-7183F4C0DE83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cdb0d9eb0d13ef3a2db7aaf260bd46c780979785","datavalue":{"value":"10.1016/0166-218X(93)E0172-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$FA01F4C3-114D-481D-9B4D-385AF3977136","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"094872ae19aaefae7b684ff42c411c46d785c7f9","datavalue":{"value":{"entity-type":"item","numeric-id":882785,"id":"Q882785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$C3B43BEA-DF22-4407-A7C6-FF34911C8A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72bb661145d847bd188af63dd7facd787002875e","datavalue":{"value":{"entity-type":"item","numeric-id":241266,"id":"Q241266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$216E2373-CBED-4609-BF4D-ECD46824E333","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":"Q1893154$7E9FB116-B50A-4299-B3D0-42F13FBBEC2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35560ff9834a057879868809cad32ac850730b23","datavalue":{"value":{"time":"+1995-07-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":"Q1893154$8243C4FF-9E29-4DF6-B259-06E1EEA7D585","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"40d648b457f434748e7bc145d1ea48f4a1befdb4","datavalue":{"value":"This paper proves that it is NP-complete to decide whether a simple, 3- connected, plane Eulerian graph for which all face boundaries are 3- cycles or 4-cycles as an A-trail, that is, an Eulerian trail in which successive edges are always neighbours in the cyclic, clockwise ordering defined at each vertex of the graph by the given plane representation and a linear hypergraph which is regular of degree 3 has a spanning tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893154$32C4E327-5A98-4F07-B6C4-327990D2DC5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$38DC6919-89AA-47A7-A7CD-B1EDE5312440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$9D1D3B1E-94F8-42EA-A136-7E0C4905366B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$3FB5DA19-6251-41FC-91AE-75102DC493F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$DD05851F-C65E-4B96-8E7B-F39C8C6904F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$CDD9D5AA-0514-43AA-B61D-9F24992782D2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5c2c16e7b6cbe597665cc389859ecf084e33967","datavalue":{"value":"769292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893154$8A10CB8C-8F62-4231-9BCF-422B8F2A602A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893154$294884C4-4B1B-4F1D-B002-5C26D67D1C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9442dd082d4beac695371f639f01792b0288c33e","datavalue":{"value":"Eulerian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893154$BCD8DB6C-D3E0-41C9-8E04-530E1A23848E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37fdb4a2d7840da529ebe452e971e96f8ad34752","datavalue":{"value":"Eulerian trail","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893154$D984167E-7654-4561-AEF3-3C716B45481B","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":"Q1893154$9258FC84-B1F1-4B83-A9C3-F1DB19E32FC1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"03542a1521a1c6883283ebf61d71a82c7bffd259","datavalue":{"value":{"entity-type":"item","numeric-id":1392551,"id":"Q1392551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$F27663FA-9E09-47D9-A414-829507788643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c9a36b40982dae6218235d8aaa21b2cd99176e1","datavalue":{"value":{"entity-type":"item","numeric-id":1090338,"id":"Q1090338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$F5690E0F-38CA-4A30-B07E-4AC615B6FD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efc49ff2244c1dfae0accc897efa1d6c3c0173f8","datavalue":{"value":{"entity-type":"item","numeric-id":5335885,"id":"Q5335885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$C01AAC46-DBD4-4B8B-BF5A-A37EF27F5144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$184305EF-CDEB-4BF7-AAB1-028AA4E869A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbf60b8621d856d80efdab97a0a055b9b53fa164","datavalue":{"value":{"entity-type":"item","numeric-id":3026383,"id":"Q3026383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$ECE80773-B981-46FF-B3ED-C55C8EF3C78D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81f55414b5f188e5326c1082a9fc31bee612d601","datavalue":{"value":{"entity-type":"item","numeric-id":1212467,"id":"Q1212467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$65183D1B-618C-4F6F-8ED1-DD12FB251AB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"019536ba97025129d85b72361c0a6180164d4313","datavalue":{"value":{"entity-type":"item","numeric-id":1188656,"id":"Q1188656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$E53D5747-4F1F-4410-8C46-9EE53A650C59","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":"Q1893154$E8808F54-D555-4255-928B-CE6CAAA829A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$E934B7DB-FBC6-481A-AFFB-22C96C433FB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$B496DE5D-DFC6-4E41-A469-9AEB96213244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fb26f90ea1a17602f04f4bf045113c100c50cd8","datavalue":{"value":{"entity-type":"item","numeric-id":3897065,"id":"Q3897065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893154$1DD4F538-38C5-4A12-876E-95EB7D9B132C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"179e5bfc1f9042f8cb32d677261fc8f3b4699295","datavalue":{"value":{"entity-type":"item","numeric-id":1392551,"id":"Q1392551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dfcae8a93980d21d0e2a1411d8ec6de81887ebc","datavalue":{"value":{"amount":"+0.8279317617416382","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":"Q1893154$96D02ACE-1C15-461A-AD6F-2E865A34B6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43b3be13b09790b54d40cca368c794fc0dbf5c38","datavalue":{"value":{"entity-type":"item","numeric-id":3703676,"id":"Q3703676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"619524b6866bbfd52303c328628e0299aab55ce3","datavalue":{"value":{"amount":"+0.8093007206916809","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":"Q1893154$BC0A424E-BA7E-48A2-BA32-04661DCA268E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ab5de5b8f7d4c1b1fe29cac17f50a1a661596e5","datavalue":{"value":{"entity-type":"item","numeric-id":1090338,"id":"Q1090338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af655006b13ba17318092859e6c484c835cb2f11","datavalue":{"value":{"amount":"+0.7807633876800537","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":"Q1893154$F999A4E6-680B-486C-BC2D-0AAFB59DAC1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52037fedab33d86780c32374982218ded98652a8","datavalue":{"value":{"entity-type":"item","numeric-id":1199472,"id":"Q1199472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e163209e8b7e85efae89db6d17a9bb1db425ff70","datavalue":{"value":{"amount":"+0.7722691893577576","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":"Q1893154$6D9E58A0-B39C-486E-9E7E-249DBDA3A025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8483c05a029ef07fef47d4c6f39c813b868e8b53","datavalue":{"value":{"entity-type":"item","numeric-id":1887070,"id":"Q1887070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"737e796689cd41af912710dafb99ab692b177a87","datavalue":{"value":{"amount":"+0.7706080079078674","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":"Q1893154$710EB250-4AB9-4A92-936F-128380FDBF82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_NP-completeness_of_finding_A-trails_in_Eulerian_graphs_and_of_finding_spanning_trees_in_hypergraphs"}}}}}