{"entities":{"Q6971747":{"pageid":21333537,"ns":120,"title":"Item:Q6971747","lastrevid":84045221,"modified":"2026-05-08T17:39:42Z","type":"item","id":"Q6971747","labels":{"en":{"language":"en","value":"Hamiltonian path in permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8052656"}},"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":"Q6971747$293C4AEE-8A96-4695-B298-6795EA84C908","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dedc8649c8896315b972149f98180ff5c79ba681","datavalue":{"value":{"text":"Hamiltonian path in permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6971747$0CB8848B-46B1-4BAC-B2D6-AB7BB41F4646","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78c9d9c66f7eca2f056ad5fd5542cc3671e54a39","datavalue":{"value":"1571.05253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971747$45510D3A-1484-4A3D-A963-5C841A0E7D48","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4f3333ec8171ff934dbd4241b4dd2016b48f7cfa","datavalue":{"value":"10.1016/J.TCS.2025.115301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971747$0A892072-3FF8-4C62-8E4F-FB4E952B7C4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6729a8c9005f83e93558e9a827d4b2df1e4a4fb","datavalue":{"value":{"entity-type":"item","numeric-id":6971746,"id":"Q6971746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$17068387-4A1A-44F8-AD79-41CF15F3C8D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"870c029946fd9f6d1d9a374a883445ef0f05e9d4","datavalue":{"value":{"entity-type":"item","numeric-id":1606954,"id":"Q1606954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$B9BD1879-B28D-43DF-AF94-C34F087704B0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$C76C95C8-F238-4D34-84C4-3A76285DAC68","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"752cbd85e48c29097ef77f01360fb6a232ac8d6d","datavalue":{"value":{"time":"+2025-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6971747$F4FEE2FD-0E58-4A31-9645-5BE39850CB60","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94c772f7a3f3eb41145b74d08bb93a72ea7d6d59","datavalue":{"value":"The Hamiltonian path problem is NP-complete for general graphs. The notion of a follow-up vertex in a permutation graph is introduced in this research, with respect to its Hasse diagram. A necessary and sufficient condition is justified for the existence of a Hamiltonian path in a permutation graph in terms of the existence of a follow-up vertex. Specifically, it is proved that a permutation graph has a Hamiltonian path if and only if it has a follow-up vertex in its lowest layer in the Hasse diagram. A number of improved algorithms are developed using the findings on follow-up vertices to find solutions to the Hamiltonian path problem in permutation graphs that run in \\(n(\\log (\\log n)\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$7552AA20-9B19-4FEC-8E30-7BC89A80D000","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"79a8c6554e98e741fdd08e23d1518b113d533e27","datavalue":{"value":{"entity-type":"item","numeric-id":175486,"id":"Q175486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$E0B976B9-ADA7-48FB-B61E-AE54D496726C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971747$6655987F-A63E-48EB-BD70-1ACB4A9E8EC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971747$88D81803-F1F7-43E2-8733-62FA2ECB78C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971747$FFD5D0D2-2399-456F-8F44-54CA983950D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f4d7b134a2c50ad7674fe9b5cb340b896121a69","datavalue":{"value":"8052656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971747$C420C998-8360-474E-B777-5F806C81D870","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$281EEA07-4F23-4E8C-A1D6-594AA92114A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ee7f91a3a095e565333b490a6f8bc374ae00cf4","datavalue":{"value":"co-comparability graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$9CC72409-F79A-456D-8E7D-E14E5DF2D100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$5A09E4B7-848F-4A79-8249-68D2C41787ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c73176671a7372845a4821e48e43363604cbba95","datavalue":{"value":"clique partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$A4CF738E-B049-4FC9-8076-ACADD2067AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45ce782da195090588818a066a1f104d5fd148cf","datavalue":{"value":"bump number","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$4D42D6AD-0CE7-44C5-BF67-4FA05DD254CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971747$7D1C7194-7912-47D0-8DCF-14B17DEE0539","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":"Q6971747$311F39EB-B4E9-4EF7-919E-932542DB9841","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a44c51b5e9e197dfa093c0f708d741121703f91","datavalue":{"value":{"entity-type":"item","numeric-id":2133251,"id":"Q2133251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$C8D1B8F7-BEB7-45ED-BC6D-EA4215B66C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4cd58bdf03fd65fc17fc45e65b2f47ab92f158a","datavalue":{"value":{"entity-type":"item","numeric-id":1208466,"id":"Q1208466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$5175C759-7D28-47D7-8AB2-FF1ED5D05582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"876fdd54303162bfd0049e7d11d97f5edc6a8ef3","datavalue":{"value":{"entity-type":"item","numeric-id":1169818,"id":"Q1169818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$5D242584-4CD9-438B-90DC-20BC9BC9E5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b98425b3d91618874e1f97c679760dcc6a7aa204","datavalue":{"value":{"entity-type":"item","numeric-id":1014413,"id":"Q1014413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$6E71BA00-90E3-4C5F-A306-F14DCEB8781D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$1FC3A47D-D7B3-4673-9653-E23C33D7DFA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b02b4f48d0037fad08c849795b6a26429a780be","datavalue":{"value":{"entity-type":"item","numeric-id":1823687,"id":"Q1823687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$A7D7CDD4-66BA-40A4-BDD3-3BFB53532AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92c907f08421493682920998b233ac32ae250a2a","datavalue":{"value":{"entity-type":"item","numeric-id":1198484,"id":"Q1198484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$349C951F-E31E-463D-A2B7-DD80A708A404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a7147a6ea242cdd731f07aa5d994b6323d39aaa","datavalue":{"value":{"entity-type":"item","numeric-id":1201106,"id":"Q1201106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$ADAD627F-362B-4626-A4B8-C8865F97B923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"405868d47a38f337608969d970fc6ab058e96a24","datavalue":{"value":{"entity-type":"item","numeric-id":4302282,"id":"Q4302282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$0AA5A2BD-9FDA-42DC-9B14-7C1DF493FAFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b11e3ddd50cc05f15257fe85c28246b429ab7a37","datavalue":{"value":{"entity-type":"item","numeric-id":5921771,"id":"Q5921771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$03FB6657-1902-48BA-BC90-5BD139D6341F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"319fdaa27484a2ebcce1969d012e31307e954320","datavalue":{"value":{"entity-type":"item","numeric-id":5663894,"id":"Q5663894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$500E8DE8-4B2E-4AC3-81CF-FC0FB6A09051","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":"Q6971747$50F7EC8D-2F0E-43A6-B03A-829C884FFDCD","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":"Q6971747$F1A30374-DEEE-4171-8B44-06C0CFB28DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$30E268FC-3402-40D1-BDC6-55EEBBE3D80B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba6c020c9b97172623cea215d03785951c408404","datavalue":{"value":{"entity-type":"item","numeric-id":3947135,"id":"Q3947135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$325C94EB-98CC-4F71-9B16-99AFEF89C382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"209a53d1b241380cdafb79969e0e9def1f032b49","datavalue":{"value":{"entity-type":"item","numeric-id":1106863,"id":"Q1106863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$55FC0D1B-86FD-4E4F-8204-752FB07A3AC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$3C7DFF71-2803-40D2-B723-2158FA13C98F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86c25efb55170e111b0e521647268283d3cee6dd","datavalue":{"value":{"entity-type":"item","numeric-id":1080870,"id":"Q1080870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$C9743FD2-A8E1-4FF5-8AC3-A908AD19232B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"140d5b5ee3e7681f006641ba2700bbb603d35608","datavalue":{"value":{"entity-type":"item","numeric-id":2489947,"id":"Q2489947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$C30F0540-6B0E-4731-B5D8-BF647105A099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3e66368e1b985a6e86f86506e55170c9e38f8e3","datavalue":{"value":{"entity-type":"item","numeric-id":2566023,"id":"Q2566023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$D48B26E1-CDE3-4566-AFC4-2C6D53BB36CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa4122382bd2f1fa19da3c03c0cb7eb5bd00b1cd","datavalue":{"value":{"entity-type":"item","numeric-id":989586,"id":"Q989586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$BF2A13D0-14E1-4047-89F8-AF389442B944","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":"Q6971747$461FDF26-DF15-45F0-9CE0-3A7DD5AEB269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f36da7f88cb96931b8c5ed2b7694309af76f9b","datavalue":{"value":{"entity-type":"item","numeric-id":5893777,"id":"Q5893777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$1EEBE9D6-4757-4C79-8A51-94E3ABA4298A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fddf78676d43f688f22d0ab9603f5b22b0a030","datavalue":{"value":{"entity-type":"item","numeric-id":1066674,"id":"Q1066674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$40831B3A-A737-4E49-B171-91E7ADFAD7E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5819b916a40dd6679d6596ec0dc1aa2484ff3d","datavalue":{"value":{"entity-type":"item","numeric-id":915465,"id":"Q915465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$12CFE71A-199F-49F0-A907-98BE7AA3184E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d71f42ea379b11c26b53ae5a6ca9e2f26814f090","datavalue":{"value":{"entity-type":"item","numeric-id":1923528,"id":"Q1923528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$71E393E7-32A7-48C9-870F-4D5143841795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$A77A158A-A494-45B5-933E-A9C8887E0DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6725c1625fb4d8df7bc9ef4203cff94df6e2280d","datavalue":{"value":{"entity-type":"item","numeric-id":1313714,"id":"Q1313714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$1930E763-33C8-4475-AEE1-AEB0990CE2F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6966529cac746c39814c4ab98e8fa0cdd728bb20","datavalue":{"value":{"entity-type":"item","numeric-id":4027864,"id":"Q4027864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$C7A84076-72E3-4128-B028-8899CD9E08F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21d190b8121424e6bf97b2b3693a3293aa41e37a","datavalue":{"value":{"entity-type":"item","numeric-id":5900030,"id":"Q5900030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$1BAA544A-0C94-48D5-A7A3-790207BF449D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$AEC70D35-374E-46FD-908A-8CAA533D58A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ba2a12b9e1e5e9bec0aede63e4f328974ff5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1241058,"id":"Q1241058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971747$6F3D7C0F-A413-4381-BA75-9922DE28B1C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hamiltonian path in permutation graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hamiltonian_path_in_permutation_graphs"}}}}}