{"entities":{"Q3057610":{"pageid":3068326,"ns":120,"title":"Item:Q3057610","lastrevid":80192492,"modified":"2026-05-06T15:38:15Z","type":"item","id":"Q3057610","labels":{"en":{"language":"en","value":"The longest path problem is polynomial on cocomparability graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5816305"}},"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":"Q3057610$8DA133CF-E2F9-456F-A375-97AA81DE6F6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5b842f91445f966c23b67a2e1dc12037f512c36","datavalue":{"value":{"text":"The Longest Path Problem is Polynomial on Cocomparability Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3057610$3DF4695F-A066-416F-AE0E-760D6497929B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5b79a8454542d669675a178eb07e4bf0395ed406","datavalue":{"value":"1308.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$CBCEA588-7B61-497B-81AB-B96AA3C06AED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"53deae0085f58e86817ec16f0660d0771e8be493","datavalue":{"value":"10.1007/978-3-642-16926-7_5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$5E0613E8-8623-4F0E-913F-D9E01392A98A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"851c83f2edafe8a4c557d6fe14116376598395c6","datavalue":{"value":{"entity-type":"item","numeric-id":639286,"id":"Q639286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$7A0D137F-C7A0-4C0F-99B7-D825E4296A3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6269fca4b2624f5addc49e1e2be512d43e29d093","datavalue":{"value":{"entity-type":"item","numeric-id":294752,"id":"Q294752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$F2D28C9C-1E6F-45F5-AB8C-37119494C23E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fdb485d5bd3f1253538b8954cec6dfa0a2ca2ad0","datavalue":{"value":{"entity-type":"item","numeric-id":3057607,"id":"Q3057607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$47C05C2B-A5F0-4F37-970A-E38865E8B66B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"427ca42c261ebc6b47b3bf362304536f6152ab98","datavalue":{"value":{"time":"+2010-11-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3057610$F9EFD1E3-BFCC-4672-9502-C4708D6C9650","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$671AA81E-1288-4B34-BD9B-7D59DA855E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$4DE9E931-81A1-4D17-A4E6-6599B0383417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$8456D3D9-34ED-4DF8-9240-32921C6C0650","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec365e7f873928b4f13803c56004466498b9b6cf","datavalue":{"value":"5816305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$E83F1F84-565A-4AE7-8E9D-90AEAA210ADE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e826d58a24639276484be95f2b31a438a61d3e6","datavalue":{"value":"longest path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3057610$AD4802D9-97CD-41C5-A818-CCE8338E9517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbfeffd12b664e76aec2f0d8ca9ba37ca2617ebb","datavalue":{"value":"cocomparability graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3057610$E6FAB93D-40E3-41EC-886A-7EAAC3C2B9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3057610$C378C4A2-54AC-49A1-A9D9-E19572BB1A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3057610$8180A138-C1FE-429B-8627-9BEC6D07E4C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q3057610$3D04A049-5543-4230-9E05-C5FA3B940991","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":"Q3057610$02508EFA-709A-435A-921B-BC0AECFD5662","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b60a860f94f05ad72d528d7f78bb09329f825961","datavalue":{"value":"https://doi.org/10.1007/978-3-642-16926-7_5","type":"string"},"datatype":"url"},"type":"statement","id":"Q3057610$0D69DD17-A6BF-4BBB-B64B-4FEF32D73759","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0da02b6c3dbe5c8efa557304f4a0754a18bf04f6","datavalue":{"value":"W1541438895","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3057610$C8663E01-B4F5-4865-A363-0247BFC6B75D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b66d43343b5e258838f8347f60921b66aa51177c","datavalue":{"value":{"entity-type":"item","numeric-id":911770,"id":"Q911770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$94EF69E7-FA26-4EC4-B550-E9FDB700D43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94da4d6600d25d4a215e4ee2b5eb2e517f6e47fa","datavalue":{"value":{"entity-type":"item","numeric-id":1957649,"id":"Q1957649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$C5F338AF-2B8C-4699-ADA3-E3B469AB2C83","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":"Q3057610$3FF82BEE-B228-4416-8216-481438E7EB70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$131F6D6E-E0B3-4B10-9E1D-B67C7BD188B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a11dfdcd3309a56302af4f694bf0296108f93a3","datavalue":{"value":{"entity-type":"item","numeric-id":1603531,"id":"Q1603531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$FDF44708-90D6-41D1-8863-46D961092416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19ddda0acfef7ef7a9158a48f353613b3545184b","datavalue":{"value":{"entity-type":"item","numeric-id":4262690,"id":"Q4262690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$70A5E8F0-5AA0-4772-AB52-D052A1751E4D","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":"Q3057610$83DC1493-F8D6-49BD-865F-41166184B437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82040db26e41ad551b2b9ee4a805cebd408e2613","datavalue":{"value":{"entity-type":"item","numeric-id":1210553,"id":"Q1210553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$6BADBBB6-7E5A-4B34-9572-83B57D192B03","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":"Q3057610$491A53D3-BE22-4D53-8B7D-868DCD4A196D","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":"Q3057610$D08F0848-78CA-4F6A-B491-19BC08F9CFEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"657c6cc86aa1cbf7ed3b48de126ccad384584e00","datavalue":{"value":{"entity-type":"item","numeric-id":2921667,"id":"Q2921667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$86DD09D7-6D0A-4303-B3F5-BA47C0B469AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72ddb9456fffb4c4ef8c52e142e980d184cc280c","datavalue":{"value":{"entity-type":"item","numeric-id":3581003,"id":"Q3581003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$785C0751-12A8-491E-943F-D3EBAB3F30F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9457545376a3dce3be2b9681bd8dbb8130ab84","datavalue":{"value":{"entity-type":"item","numeric-id":3597877,"id":"Q3597877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$F5CB9710-E7D7-4CDB-8F80-31F7A7CC0F1E","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":"Q3057610$92315E19-A8F3-4A4E-8779-DE89461F9125","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":"Q3057610$5C58F3D8-467D-42D0-957C-99A770052444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b07b5dcf0b43c9f49e2d29db88bee73b1cb11be","datavalue":{"value":{"entity-type":"item","numeric-id":1886097,"id":"Q1886097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$64A01430-2ACD-4C1A-A1E9-229FF15FF735","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":"Q3057610$CC65F480-94B6-496E-AC17-F09BA984C403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"817a0d1b57b93cd395ace45fddc3b62ca58f0fef","datavalue":{"value":{"entity-type":"item","numeric-id":3182942,"id":"Q3182942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$CA41A2BF-28A4-4A19-9DA4-26F14845F735","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":"Q3057610$C44245CD-406F-4713-A73C-17E975DC9008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2df50d8783feded12a64b982501eff223d28a73c","datavalue":{"value":{"entity-type":"item","numeric-id":4231782,"id":"Q4231782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$F7CA1354-33AE-4484-90EE-2D18B5FA8098","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":"Q3057610$3AB88A57-00C8-4DD4-B97C-94693E0DE749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23d0ccdd82231b87b80b9ca8cf6636ef387a162","datavalue":{"value":{"entity-type":"item","numeric-id":1262132,"id":"Q1262132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$DF43939F-A167-428F-9B85-DE2094D9BDC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a30628b05cd6fc17435ca4cf1e696fc5812bfee","datavalue":{"value":{"entity-type":"item","numeric-id":5452149,"id":"Q5452149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$E5E115E1-849E-423D-8052-AC506EC19635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29ccd0189a93523a1b270b425ed7f41b9220c33b","datavalue":{"value":{"entity-type":"item","numeric-id":5712173,"id":"Q5712173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$F4F59641-59B5-44A7-B269-349050D8757E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c3370588620c9df763ccd44ae599ab86dc9999a","datavalue":{"value":{"entity-type":"item","numeric-id":2379947,"id":"Q2379947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$0A975FEE-439B-4B75-A454-249EF4406E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af7cd9bda54a7d3d1025b148944f87f87d4aa2c7","datavalue":{"value":{"entity-type":"item","numeric-id":884457,"id":"Q884457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3057610$E965E22B-5AD7-4022-9AA8-46FDF1FDA9D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42c373083c1f93e8eab9108ee7c225c7b67cb0bd","datavalue":{"value":{"entity-type":"item","numeric-id":1939666,"id":"Q1939666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9984896fa06f504f8601be9bbfd81cc0956adeb","datavalue":{"value":{"amount":"+0.999848246574402","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":"Q3057610$C5A3BB4B-D924-45BA-88D5-A715D0A20880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a48c3a41f7975849124c781462fb1c6b9a26060d","datavalue":{"value":{"entity-type":"item","numeric-id":4899036,"id":"Q4899036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e5b1c7e10dcc701d359f6bf0a7097ff6ee953eb","datavalue":{"value":{"amount":"+0.9105398058891296","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":"Q3057610$70DC8F09-7AF3-484A-B4B0-242A610BC8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"544ee5250225771ba6f537e2212ce56a6c200898","datavalue":{"value":{"entity-type":"item","numeric-id":3182942,"id":"Q3182942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a5ded07b68228ca806765a7d1900fca8e36cd23","datavalue":{"value":{"amount":"+0.8595452904701233","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":"Q3057610$AE253A1A-2816-4E2A-8744-D99CBD3FBE60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d602950929f9362ce41facdb588d819e2306460b","datavalue":{"value":{"entity-type":"item","numeric-id":639287,"id":"Q639287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab082bcb9db51d25957a1423da2a30222235d289","datavalue":{"value":{"amount":"+0.8374791145324707","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":"Q3057610$7DE000E2-BCEE-4589-960F-9A7A431355BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3659bf980b22aa2e275ed6cf0fb8f66b60b5bc26","datavalue":{"value":{"entity-type":"item","numeric-id":5712173,"id":"Q5712173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63035059681375e0ce72cdd70b9517416af1b021","datavalue":{"value":{"amount":"+0.832249104976654","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":"Q3057610$0BC4C84D-3FE7-4060-B467-1118265AFC63","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The longest path problem is polynomial on cocomparability graphs (scientific article; zbMATH DE number 5816305)","badges":[]}}}}}