{"entities":{"Q1406033":{"pageid":1416773,"ns":120,"title":"Item:Q1406033","lastrevid":68630532,"modified":"2026-04-13T01:03:12Z","type":"item","id":"Q1406033","labels":{"en":{"language":"en","value":"A polynomial algorithm for finding \\(T\\)-span of generalized cacti"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1977904"}},"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":"Q1406033$963144A2-5B24-45C3-B53C-8F2E938DEFD6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8033ad7abeeddda6395ca5d6dcf34a394bf88ecc","datavalue":{"value":{"text":"A polynomial algorithm for finding \\(T\\)-span of generalized cacti","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1406033$FBD98B2E-DF29-41D1-BCE6-4B82CFC615AB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa4638811c27a3af1ea5f2859a005c541954b4f7","datavalue":{"value":"1023.05125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406033$1639D8B9-0172-4A77-84DA-EC5F392550F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"31ae8b768173ed958270dd9a59f97f7f7b03d4db","datavalue":{"value":"10.1016/S0166-218X(02)00575-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406033$64BA3A41-908C-47A4-9E4F-BE4FA1D2128A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"df859106777b262ea1e16ccf8d0885099b524191","datavalue":{"value":{"entity-type":"item","numeric-id":177037,"id":"Q177037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$47E91B69-FA2D-415F-84E3-8DC332C90C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e77dc62432e0084fdda4e3c056dc8f26060354d","datavalue":{"value":{"entity-type":"item","numeric-id":186209,"id":"Q186209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$69A3C8BF-8182-454F-8307-EADA7C27C85C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"681fa36f324bfdb5f85fc6878945cb77d35a0028","datavalue":{"value":{"entity-type":"item","numeric-id":237430,"id":"Q237430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$8E6810B7-D894-4632-91F6-AC51C8AF200D","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":"Q1406033$CB9E1317-B02A-4810-B787-8BC1AB3E3A3B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5a3bd22b3255d28cafbe1a32be16f369f6f38fa5","datavalue":{"value":{"time":"+2003-09-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1406033$427E6EC1-76D6-45CB-A648-BC85181BE633","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"176154fbbfec0e698085a9e2aa9d5597de20dc8b","datavalue":{"value":"The authors study basically the minimum \\(T\\)-span problem for a diversity of graph classes. The general problem was proved to be NP-complete in the strong sense, however for numerous instances of the general problem exist polynomial-time algorithms. Subject of the paper are thorny graphs. The authors claim that, by the general algorithm for the problem, numerous classes of thorny graphs posses polynomial-time complexity. Nevertheless, the results for cacti are a little bit doubtful. The main reason is that the authors claim that the thorny graphs are planar and they use this claim for arguing. However, it is in contradiction to the famous Kuratowski's theorem on planar graphs. So for the time being the obtained results must be restricted to planar thorny graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406033$BFC51E1C-0837-44D5-AE0C-A61192926930","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc368e3db50c98d6dbe7e70c58f215b9063f9066","datavalue":{"value":{"entity-type":"item","numeric-id":1406029,"id":"Q1406029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$668A8887-E925-499D-8506-FA5FAA82D5C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406033$7FFD4AE5-0A60-4215-8391-91689937C57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406033$14A5D525-9ACB-4682-888C-FD0F7A8CBC29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406033$A5ABA80A-3C44-4EBD-B8DF-85256F13D5D9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76a66a4567afc617807668ab83b92f07785e0490","datavalue":{"value":"1977904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406033$21B1028B-C63A-4D0D-8FB6-C95257FF721B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b75cbb2d18150a13cebcba9219381a55be466901","datavalue":{"value":"T-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406033$F85C4467-A213-48D3-B1A9-4D8CFA584C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f62d3e777b533be1380995440335bacf9afdfb6","datavalue":{"value":"T-span","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406033$0817EE7D-7AF5-4148-9925-71C4EAEB2BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62013111d4b62764405e677d11e3389df026653d","datavalue":{"value":"thorny graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406033$34D9EF96-671D-488F-A6C5-5CEEF681FB51","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":"Q1406033$765FD44A-05DF-4767-8F81-2462197AC09F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c26c0e8ab719150b99b971f6f16d3f7da40826d","datavalue":{"value":{"entity-type":"item","numeric-id":3322121,"id":"Q3322121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$35EA3D1C-F97B-4213-9E49-4F43573B21FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06a41539dcc4a265ec1ddfd6fa80a01b86565bd0","datavalue":{"value":{"entity-type":"item","numeric-id":1406032,"id":"Q1406032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$83996C9B-CE61-48B1-AF22-A60C6AE3B86F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96f66bae46d865eb8097221122d7ee8e3c009600","datavalue":{"value":{"entity-type":"item","numeric-id":1297406,"id":"Q1297406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$1ABC1CEF-BC2C-48EC-876D-A93558C6B3AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43933941143ee0993fa68b65eabdf09970b1e098","datavalue":{"value":{"entity-type":"item","numeric-id":1918544,"id":"Q1918544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$C03C0ED3-F0FA-4EAB-9B7E-77295EFA2D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0363418f97e59fb1936c27121e237a5c19ded3e7","datavalue":{"value":{"entity-type":"item","numeric-id":1197028,"id":"Q1197028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$32E60B52-800C-449C-B028-81C890911948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38b2e34bca0883dbb374b66c8b4e7bde85e93dcb","datavalue":{"value":{"entity-type":"item","numeric-id":4317706,"id":"Q4317706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$ECB30752-1C27-473F-9479-FB4E9014490C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6e0627601eb678357cd6a182e4c3a611cabaca","datavalue":{"value":{"entity-type":"item","numeric-id":1182897,"id":"Q1182897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$822B5128-DC9E-4722-91BB-608FB2762636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b048e550daccef3ab3d36df1ef2635b07519043","datavalue":{"value":{"entity-type":"item","numeric-id":1309815,"id":"Q1309815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$65E9E705-F054-419D-A9CA-46511160A56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"467f7ee48686ce3c5da8b77251bcc4bbf0d6a360","datavalue":{"value":{"entity-type":"item","numeric-id":3487366,"id":"Q3487366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406033$64FB060E-51DC-4326-B432-462BDBAF075E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b760fdefbc0602b2d1f68dccad59f7ebb459aa3b","datavalue":{"value":{"entity-type":"item","numeric-id":281767,"id":"Q281767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75b979f2e794d132ba4a41faaa22a232abf7d964","datavalue":{"value":{"amount":"+0.7479103803634644","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":"Q1406033$B1923A3D-3A80-4045-BFF7-5C075C574A52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60d8a9307dff2e61861482a17311cc8a468c7b1d","datavalue":{"value":{"entity-type":"item","numeric-id":4232796,"id":"Q4232796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc42ef0e3d4fc96e9a2d91e3d9c486f82d552e2b","datavalue":{"value":{"amount":"+0.7468470335006714","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":"Q1406033$CCBEF425-BC94-40D9-A1E8-0B21F2D851EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eeada3051f7afc91631aaf2952c3d21cc7eb6a6c","datavalue":{"value":{"entity-type":"item","numeric-id":3521950,"id":"Q3521950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc42ef0e3d4fc96e9a2d91e3d9c486f82d552e2b","datavalue":{"value":{"amount":"+0.7468470335006714","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":"Q1406033$7EA65394-0305-4874-AB3E-23563F4956DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1edca5073194ecbade83b3f30e951df4ac19431","datavalue":{"value":{"entity-type":"item","numeric-id":4373672,"id":"Q4373672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"856b432610687c58d83fdbad4ea5db7939b6749c","datavalue":{"value":{"amount":"+0.7433725595474243","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":"Q1406033$79CD2B56-9310-421A-8EF7-83F48779C1DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"160d0808e87b2ed57f526c3751417d6a6d9f8827","datavalue":{"value":{"entity-type":"item","numeric-id":1759874,"id":"Q1759874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7610d93d2e441fc76ed7cfb086e8302bdfa3b9a2","datavalue":{"value":{"amount":"+0.7426828145980835","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":"Q1406033$A3D2CCD0-55FB-48B8-887C-1BC4F033A5AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial algorithm for finding \\(T\\)-span of generalized cacti","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_algorithm_for_finding_%5C(T%5C)-span_of_generalized_cacti"}}}}}