{"entities":{"Q1349101":{"pageid":1359840,"ns":120,"title":"Item:Q1349101","lastrevid":47914630,"modified":"2026-01-03T01:58:23Z","type":"item","id":"Q1349101","labels":{"en":{"language":"en","value":"On approximating the maximum diameter ratio of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1743031"}},"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":"Q1349101$C52B9E59-1292-459F-BC09-DFA4C8EDCCA6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"65e80781c5218e278bb71521c6d398ce5909b995","datavalue":{"value":{"text":"On approximating the maximum diameter ratio of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1349101$DC6FD224-D40F-451D-886A-1B298503C8F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"857578330b43e76b62e0ca8c31c4a498dd2411fd","datavalue":{"value":"0999.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$4F494D31-B736-4951-9AA7-531D89EC7CF0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e24062ba9ead6d5ede1c03ee4a73ae2aacd36b63","datavalue":{"value":"10.1016/S0012-365X(01)00091-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$E86717B9-BAD4-4EA6-A7D7-FAFB962A4AAD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65777c8c2dcef95d5fc4cb8f801c29b1e6cef34c","datavalue":{"value":{"entity-type":"item","numeric-id":1349100,"id":"Q1349100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349101$8D25FEBD-B4B6-4AFA-91E5-84A9FA5FA1C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349101$42EBC58C-C68E-4BE0-AB74-D522A87E5125","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349101$A1F52211-91FA-4922-85A4-8935E765EE99","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cda08edf6e14c28a948f9b78f5bc4351bb49e6b0","datavalue":{"value":{"time":"+2002-05-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1349101$7056F336-CCF5-4D04-BEDC-9D2B31FD2D27","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"586648959b217441d97831ec46eb16a4b550ae7e","datavalue":{"value":"It is shown that the problem of determining the maximum diameter ratio (local density) \\(\\text{dr}(G)\\) of a graph \\(G\\) is APX-complete, i.e. there is a polynomial time approximation algorithm which approximates \\(\\text{dr}(G)\\) within factor 2 but there is a constant \\(c> 1\\) such that finding approximations within factor \\(c\\) from the optimum is NP-hard. The authors also prove that for every fixed integer \\(d\\geq 1\\), finding a subgraph \\(H\\) of \\(G\\) with maximum number of vertices whose diameter is \\(\\leq d\\) is polynomially equivalent to the MAX CLIQUE problem. If \\(d\\) is the diameter and \\(n\\) is the number of vertices of a given tree \\(T\\) then computing \\(\\text{dr}(T)\\) can be implemented in time \\(O(dn)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349101$E93F0E14-F410-4638-8711-3160866ED545","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$A8180A58-0C9D-4533-845C-4FA5B2060706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$3F55BE60-F756-4FE8-BCA9-CD08FFB1A2FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$0E59A3EB-1F0E-46BC-8DD4-DD0E04C20740","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"523011538303c1567bbac5be64ae537f2362fb2d","datavalue":{"value":"1743031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$08ECFA1B-8DC3-41BB-99B9-E64FA68178A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc2e6bde6f0fc618014fc2c77b5f9812f6d0d7c5","datavalue":{"value":"local density","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349101$288B22E5-6D16-40FC-96D8-7736D7203AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72ed2c408b3229e22067f101036489dcb609e41c","datavalue":{"value":"APX-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349101$BB02E404-8790-4943-989F-1B2AA054C1F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349101$1EDE0CF8-1998-483E-B2ED-160189AA8724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349101$0042804C-30A2-4B01-8444-D877893F584E","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":"Q1349101$C8492EBF-4345-48A4-BDE2-CE6EDDE174A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a7cd8c8392ccf57dc3bd828c5983979a1a69b68","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00091-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1349101$936207C6-F94F-4FA6-86B1-F2473AD7EF24","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"45420248a43741c58bdee8faa3d2c44c3c8f9d01","datavalue":{"value":"W2013563568","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349101$3D5642F2-C64B-43E4-BAE6-8A649B870DBB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"071c4ed5e1c71c7d418be3f6c589bf39a76811d2","datavalue":{"value":{"entity-type":"item","numeric-id":3557054,"id":"Q3557054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f00ae5a3c7d18aef834c501ee61120a5982bfc9","datavalue":{"value":{"amount":"+0.8265605568885803","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":"Q1349101$8E661ACD-4237-42D2-8B52-FB3E9E655889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31498254e21f4b373dada85cdb8d74b3b17e85ed","datavalue":{"value":{"entity-type":"item","numeric-id":5115768,"id":"Q5115768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29c3f07883cc0595623e60a420426c6be36b4905","datavalue":{"value":{"amount":"+0.7668300867080688","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":"Q1349101$6F5107F3-0A18-47C3-84AF-0E805BFBA5E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5194c3c305bd9a45ee8ca8963b96cdeb6c50b318","datavalue":{"value":{"entity-type":"item","numeric-id":3467873,"id":"Q3467873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd57036b1e33d37ac4f61371a3bb749348c9be8c","datavalue":{"value":{"amount":"+0.7572699785232544","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":"Q1349101$5F3B1754-BE8B-422D-958B-EEF4B5CE18E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b2c4fdf861518fbf86cd4b98d0587875f9ccf9d","datavalue":{"value":{"entity-type":"item","numeric-id":1635712,"id":"Q1635712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"143f8844c8b797c51a44538bcb56539d95e4011c","datavalue":{"value":{"amount":"+0.7502789497375488","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":"Q1349101$1F49D267-BBFD-49B0-9942-0372F4F7C6A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdbe4611ca9c39de489cf0c79797e989e96c5ebc","datavalue":{"value":{"entity-type":"item","numeric-id":3325768,"id":"Q3325768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d86ec3dc7dde80b6545513f1ee92a8398934d0c","datavalue":{"value":{"amount":"+0.7457504868507385","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":"Q1349101$33474BEB-18AE-4AE7-9928-138BB05B0217","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1349101","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1349101"}}}}}