{"entities":{"Q1262132":{"pageid":1272882,"ns":120,"title":"Item:Q1262132","lastrevid":68323101,"modified":"2026-04-12T22:56:19Z","type":"item","id":"Q1262132","labels":{"en":{"language":"en","value":"A note on the Hamiltonian circuit problem on directed path graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4123306"}},"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":"Q1262132$1EB7C769-2A88-4367-9EFC-3DFEBF35B9BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e80bee5b38fd7221d5566615084dfffc8253603c","datavalue":{"value":{"text":"A note on the Hamiltonian circuit problem on directed path graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1262132$9CC3BFDF-8A6D-40A2-85B3-127B7D791CB5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c99595f711076b6f3f2b31ae660aad32879b9875","datavalue":{"value":"0685.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$B8C66FAC-C450-44BF-88FF-D0A1F10715CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c46250de0d3a8c9b6b37470276683775a7e71354","datavalue":{"value":"10.1016/0020-0190(89)90038-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$83F37672-D4AB-4480-BF9A-8F725D64236F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fca5f1c873ac4219270445309072bf83f6c59b9d","datavalue":{"value":{"entity-type":"item","numeric-id":176423,"id":"Q176423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$A88F9A8A-9DAB-4C57-804A-7397F9163BE0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$9CF3594E-2742-4280-AE75-301A9DE804EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1262132$2E6AA174-5833-4824-A160-21D9FD83E8CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6dda6cb290fb5dcac5ea871212ca5dce1c187b3","datavalue":{"value":"http://digital.library.wisc.edu/1793/59108","type":"string"},"datatype":"url"},"type":"statement","id":"Q1262132$EE61917E-39CA-4D42-8907-148446C18F78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"66c0d3a2ce87bf09ea5dadb2b558d0a90b01624e","datavalue":{"value":"The problem of finding a Hamiltonian circuit (HCP) is a well-known NP- complete problem for general graphs. It is also known to be NP-complete for several special classes of graphs. The author shows that HCP is NP- complete for directed path graphs by using a characterization of these graphs in terms of their cliques [\\textit{C. L. Monma} and \\textit{V. K. Wei}, J. Comb. Theory, Ser. B 41, 141-181 (1986; Zbl 0572.05049)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262132$98D966BE-0068-4037-803A-964C1C8585FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$6145E513-251C-4A1A-B126-0625CD37174B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$74C75CF0-285A-4641-B9D8-05027E432DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$4D492AC7-9265-4F36-BE1D-BF9F89C62F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$570A7339-18C4-43B2-ACC6-34A619B30138","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8341b8082d905333ada5e4b56e283e0ae9f04f5e","datavalue":{"value":"4123306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$055C9641-CE80-47D5-B775-D9787CEB3954","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8492362146b232473140762e4eb450db7e5af4a5","datavalue":{"value":"Hamiltonian circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262132$FA558F1E-0330-4C23-939A-45DF77DE99E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262132$29F3661D-6A8F-45DB-8EF3-EFE57FF7413E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99ead631af415d10ec7936e368ee8c3371791647","datavalue":{"value":"directed path graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262132$5B396719-8256-4A73-A1DE-B5F4FC77D8BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262132$8A56ACBD-753B-43D5-9E4E-B5E8D76FBBDF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a201a8779f110985d707176577b688d9a6216e1","datavalue":{"value":{"entity-type":"item","numeric-id":649735,"id":"Q649735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$06933DB2-CDB5-4347-A421-25A20B5A7BAC","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":"Q1262132$4B1F1B4C-031B-4D1D-A176-F97FB5A6F48B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ccef3c33f3f41ff096c3a338cc85a0a96ff3daa3","datavalue":{"value":"W2127206007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262132$D72AD988-5351-4930-ADFF-6763DD384FD5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"db695381606ba322df78c7a9c05e7660a22ed7b4","datavalue":{"value":{"entity-type":"item","numeric-id":3888545,"id":"Q3888545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$C0CBACAA-2E0F-4FDC-B055-E9856DF63DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5945f050a45bd43d698004e6b0e2b06dd2fb562e","datavalue":{"value":{"entity-type":"item","numeric-id":1092669,"id":"Q1092669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$8E487914-2D94-4558-9EF3-66D5CD53F01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$58096648-DDDA-49C8-B6B5-848E8AF86659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b585dcdf59f4fe85026177ef1a61272465233d40","datavalue":{"value":{"entity-type":"item","numeric-id":3892276,"id":"Q3892276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$D5C7EDEE-E866-483A-B526-4AD34579B6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc63891e4bfc3488caa68ff8e6c76e9b7a919e87","datavalue":{"value":{"entity-type":"item","numeric-id":3684150,"id":"Q3684150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$D6B4518C-662D-49A5-ABE6-79C7C3B6CBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa97f0110ceefce3316c5fbe9c21778948ad688","datavalue":{"value":{"entity-type":"item","numeric-id":4742820,"id":"Q4742820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$8DE5A1B9-F568-47CF-800D-B1416360E11A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$B1720234-3F83-4746-A33F-C39B2CE63FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff0493b055da35184afed510bb784ad8a891491e","datavalue":{"value":{"entity-type":"item","numeric-id":1077439,"id":"Q1077439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262132$D275007A-43BA-4EC8-9126-0E672AE1634D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ee4fdef69ee1f6bc617327c540d07b8e52cc14d","datavalue":{"value":{"entity-type":"item","numeric-id":5202208,"id":"Q5202208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baaefa7d707d552bc0b37ed6693481ed63f62b9e","datavalue":{"value":{"amount":"+0.9076487","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$6693BFF2-DD8C-4920-9C42-B36B6D0F8BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35835d8fe16a8d2e28a1753af7c850b8207c76ec","datavalue":{"value":{"entity-type":"item","numeric-id":2835661,"id":"Q2835661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04f90e350a6a2f034448d2a48f9a6a4ae3bca62e","datavalue":{"value":{"amount":"+0.9073597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$AFF8CFF3-4010-4EC8-BB24-C1037AC9D0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d978ce98a77456084349d24b5d708b3363f1b4e","datavalue":{"value":{"entity-type":"item","numeric-id":412269,"id":"Q412269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa8fda0e7978b1de0fb31d832118e6cfbdc9ffde","datavalue":{"value":{"amount":"+0.90639955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$C966F678-5A9F-4BFB-9A8F-965731B97C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16ad9193795738d46743cbd99b24d17e7379a6d7","datavalue":{"value":{"entity-type":"item","numeric-id":3819098,"id":"Q3819098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"438cdcefffcd142ca13ebe6d5df0824e2cf90473","datavalue":{"value":{"amount":"+0.90633416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$2FD2A99E-12E3-45FF-8F11-E6D36B9D81BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8278fc957bebbd591a746220dc419dddd816b47b","datavalue":{"value":{"entity-type":"item","numeric-id":1814249,"id":"Q1814249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8014999d7ed8d4589a2c5a706421c4a58557e4f","datavalue":{"value":{"amount":"+0.90521705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$35CDA14B-B01D-4939-9AF2-E6911D8B506C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfb14f62972a84d5a0d90f611f40461c6c0f89e7","datavalue":{"value":{"entity-type":"item","numeric-id":1313856,"id":"Q1313856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a213e3df580b9a342c638a39aa9289b70fca4169","datavalue":{"value":{"amount":"+0.9050137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$35B3335A-A7AD-4BE7-97C4-4966928F2150","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac81a972ef095767795b4d4a6b95a24998f55ff6","datavalue":{"value":{"entity-type":"item","numeric-id":2357671,"id":"Q2357671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"053cbe2e1371f2434b9893db759f61f5a2ecddb3","datavalue":{"value":{"amount":"+0.90447426","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$A2C868F4-8FB7-4075-94BE-46B4596CA61B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7284bc3cb84eed3263036aa649ecb8a4a99c6953","datavalue":{"value":{"entity-type":"item","numeric-id":2143132,"id":"Q2143132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf456d04e0e529ef3f630831169a9c01ed921821","datavalue":{"value":{"amount":"+0.90414214","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$3264E03C-3B86-4D40-B2DE-E5080BE94C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18bd19eae43435ec46fcb93ae697ffa1fd5e4ef3","datavalue":{"value":{"entity-type":"item","numeric-id":1302144,"id":"Q1302144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8a4ead4d47b9e96af5aae5e7a7edbed12daa0d9","datavalue":{"value":{"amount":"+0.8993529","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$300FBF29-0A6F-4677-BEFC-B3BBA9C2E3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99d25082398965de5678896e6c17456ffb8c2c2c","datavalue":{"value":{"entity-type":"item","numeric-id":3803149,"id":"Q3803149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a867107598bdabd7c7b92f43f1229887a30b7282","datavalue":{"value":{"amount":"+0.89901924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262132$F724D5A3-0574-47AF-B148-BC40573966AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the Hamiltonian circuit problem on directed path graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_Hamiltonian_circuit_problem_on_directed_path_graphs"}}}}}