{"entities":{"Q1066674":{"pageid":1077426,"ns":120,"title":"Item:Q1066674","lastrevid":48870766,"modified":"2026-01-06T01:23:10Z","type":"item","id":"Q1066674","labels":{"en":{"language":"en","value":"Finding Hamiltonian circuits in interval graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3926259"}},"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":"Q1066674$8D1FEBA4-4A23-4AEE-B6F4-BF27BC98F7A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2e08ed73ad68d49b1e1d625e49a952fb6e51f63","datavalue":{"value":{"text":"Finding Hamiltonian circuits in interval graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1066674$8C128F46-0B06-40EF-B9A9-53044503E711","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1f90a27ad9bc8cd6f1ae2fad60b963d607e3ce1d","datavalue":{"value":"0578.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$FBC4C265-577A-42D1-8736-3731B4295141","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"92882efd59e11e58fe9469610652f3d8f6f19d69","datavalue":{"value":"10.1016/0020-0190(85)90050-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$DB0316F1-17FD-476A-89BF-7309B92B687E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"725145adf60736a410a92f7f2d72d3094c36ae9d","datavalue":{"value":{"entity-type":"item","numeric-id":680147,"id":"Q680147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066674$80686081-FA4F-4EC6-B1FA-25721715B445","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":"Q1066674$242664A4-A4C5-466F-85EC-B2E2DC7698E2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1066674$5652B5A6-E5C6-439A-B269-8D178AA6195F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3dc31ec1d6eefbd13475da8907333c509e5d736","datavalue":{"value":"The problem of deciding whether a graph has a Hamiltonian circuit has been shown NP-complete on many restricted classes of graphs. This paper adds to the classes of graphs for which a polynomial time algorithm for the Hamiltonian circuit problem is known. A linear time algorithm for the problem in interval graphs is developed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066674$CDB5625B-7413-4E4F-B5F6-8502CB080A9E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$DF48EA33-CE86-4FE3-93D6-583A1152A6E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$31A8989B-6E65-4BBA-93AF-1EA69F9FB9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$4CF9C73A-6E66-4F33-B534-B64AC2E14F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$60DFF743-4826-412C-852F-F65522B7D463","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1bb108990422aed127d65755f1229c9463d415d7","datavalue":{"value":"3926259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066674$6AD18FB6-9ABF-472D-8238-88E880158D05","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066674$92E4CCFE-3665-49DC-AF4F-0378BFC55A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066674$370507EA-17B9-4524-AECC-F93C5691245F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d59ab2c83e0dbd443ebc1f3d0412b712509c0917","datavalue":{"value":"interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066674$604B201B-9E03-46B7-B337-E1B5870BEDA2","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":"Q1066674$9A2E25AE-0235-4360-9902-272FF148CA33","rank":"normal"}],"P223":[{"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":"Q1066674$E0BC9699-FC35-45DF-9288-6E6F82D97469","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb58559dbcbec2468b43206f2492cdb153b63a53","datavalue":{"value":{"entity-type":"item","numeric-id":1050117,"id":"Q1050117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066674$B5AF1E01-A537-440F-BA82-7D988E545032","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":"Q1066674$F700349D-AD83-45E4-A124-33D3638E8A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7415b51a2e51543478330c9761393acb2c869484","datavalue":{"value":{"entity-type":"item","numeric-id":5331785,"id":"Q5331785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066674$E3E00AFE-93DE-4E87-A6C2-A3BDCF35339F","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":"Q1066674$8A27ABE5-D522-4371-AD0C-B1400F6111C4","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":"Q1066674$D0A0AF30-56DA-47F2-9F8E-4E15A1C4A2C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066674$331A3CF8-699B-41AF-97F1-C4F9D6F1E451","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":"Q1066674$AB60E377-382D-4732-8934-7162A9BB7E57","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":"Q1066674$CDA5BEC9-8F13-4FC5-9C56-94025BDD92DD","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":"Q1066674$708C7949-C583-48B1-9A91-D5F8C45CA99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066674$3EE1A45B-7808-4F16-ADBA-BEA1688A4295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066674$35041D76-F3BE-4923-97F0-A5BDA1A2CF7D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49bb6bb61193159df098df774c84765b415eee49","datavalue":{"value":{"entity-type":"item","numeric-id":1092669,"id":"Q1092669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bea1b482cff3c20a28038da5d31ef16b5e3309e","datavalue":{"value":{"amount":"+0.92085862159729","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":"Q1066674$D1B76018-8301-454C-B691-00EB7E4E6AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00884b33a3803869663f98115c5da7c81e918ec5","datavalue":{"value":{"entity-type":"item","numeric-id":989586,"id":"Q989586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0865b54ae623950d3c41f8dd1b74925aa021516b","datavalue":{"value":{"amount":"+0.8419912457466125","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":"Q1066674$9726F929-B540-4AFE-A9B9-905B0465D4F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62c1fd7c9a262d20aa5bc354bb03ad7f59f13520","datavalue":{"value":{"entity-type":"item","numeric-id":1210553,"id":"Q1210553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0773dbe9d43d16c26b900883b34fabfacd0e8a09","datavalue":{"value":{"amount":"+0.8338198661804199","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":"Q1066674$8475BFEF-0E5E-494C-8887-FD0E0A4A9EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76f9b27cf2cd5c8e07083604b70aa263cfb35525","datavalue":{"value":{"entity-type":"item","numeric-id":4027864,"id":"Q4027864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dddf4d66829f048d681a3c0e64e59258d189a0ae","datavalue":{"value":{"amount":"+0.8205730319023132","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":"Q1066674$C7D0CA48-6C25-47EE-8410-95B5CE404D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f112d2e7691064911715665b570ec8208ac5c2e","datavalue":{"value":{"entity-type":"item","numeric-id":4242795,"id":"Q4242795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32e4e4139e8c9208d5759f99356236bb93ece8f7","datavalue":{"value":{"amount":"+0.8161380290985107","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":"Q1066674$8418B11F-74BF-4716-AE48-58EB0CAA1932","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1066674","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1066674"}}}}}