{"entities":{"Q1762946":{"pageid":1773688,"ns":120,"title":"Item:Q1762946","lastrevid":68895006,"modified":"2026-04-13T02:57:17Z","type":"item","id":"Q1762946","labels":{"en":{"language":"en","value":"Fault-tolerant geometric spanners"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2133694"}},"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":"Q1762946$3DEB0329-A135-4606-90DA-AEF865411613","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57e0c4239d6476c7ed8f3d9517929c74ad5aca39","datavalue":{"value":{"text":"Fault-tolerant geometric spanners","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1762946$B05CA84E-D3E1-4CCF-91FF-19BDDE9FE1B7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f01a0053ab1fe09db3b64669ef6a1f53da337e12","datavalue":{"value":"1095.68125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762946$DE969A73-7D70-49C7-B4BE-FCF4FFF05F82","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f613fb6a77a89072092d96a4db8693a9802128f","datavalue":{"value":{"entity-type":"item","numeric-id":590542,"id":"Q590542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762946$8878E88B-2DD0-440E-9100-D7C79864B056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e85103845c74f03c4ecf90171d80d2e83494147f","datavalue":{"value":{"entity-type":"item","numeric-id":319145,"id":"Q319145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762946$63CF670C-72CE-4454-8244-CA3BC943FDEE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762946$2EF532E4-7060-44CC-86AF-FD34E85A3F04","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5596d9d431c014306023aa27a7b00ce60a426d45","datavalue":{"value":{"time":"+2005-02-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1762946$B5C23DB6-96D6-4C3D-94F0-CFEB4E91CF0A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6740eb98bd03b51eaee17d35f36bb31e06ae411b","datavalue":{"value":"We present two new results about vertex and edge fault-tolerant spanners in Euclidean spaces. We describe the first construction of vertex and edge fault-tolerant spanners having optimal bounds for maximum degree and total cost. We present a greedy algorithm that for any \\(t > 1\\) and any non-negative integer \\(k\\), constructs a \\(k\\)-fault-tolerant \\(t\\)-spanner in which every vertex is of degree \\({\\mathcal O}(k)\\) and whose total cost is \\({\\mathcal O}(k^2)\\) times the cost of the minimum spanning tree; these bounds are asymptotically optimal. Our next contribution is an efficient algorithm for constructing good fault-tolerant spanners. We present a new, sufficient condition for a graph to be a \\(k\\)-fault-tolerant spanner. Using this condition, we design an efficient algorithm that finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bound for the total cost.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762946$89F940A8-C38B-47F6-87B1-92AE603A86BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762946$0438DFD1-A3B9-49B0-8176-7CEB968F4175","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9b31663c5c4bb84b09855cdffbe370fc99102a62","datavalue":{"value":"2133694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762946$A095BD0D-6C92-492A-B3C8-69B9A689F032","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c01433323618144edfc4c4e0fd4f33aad37fce5c","datavalue":{"value":"edge fault-tolerant spanners","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762946$B86A7E8F-C05F-4B85-8B7E-C101A7FD0E25","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":"Q1762946$CDC1ABC5-3020-4B61-A34F-9A9FFFC45169","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6857dacdebbc49804373db8f7ab6e3f1940f1327","datavalue":{"value":"https://doi.org/10.1007/s00454-004-1121-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1762946$21786596-D272-4BCF-BCA0-BD9CEA957853","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a51a54514b090ec7c44b6d93c5b7ad05b84e9e22","datavalue":{"value":"W1965127928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762946$17B9B470-8F60-4436-84C0-758228225F08","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cae72711866070951f02c902c0b3ace5bf0cdefd","datavalue":{"value":"10.1007/S00454-004-1121-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762946$F12DA4DA-8DB0-4BDA-A79D-F7DCA8A16E93","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3273e51338558f181964f1e2bf5c94e02cebae3","datavalue":{"value":{"entity-type":"item","numeric-id":5361598,"id":"Q5361598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$DD5F3D93-1E22-4B3F-B0D7-0AF703297EF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4494017b909ada8631d5d0a1d3bcd745aac5034","datavalue":{"value":{"entity-type":"item","numeric-id":4542536,"id":"Q4542536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36f44e6b6aa704d82dca9a363174a870b80bcc5a","datavalue":{"value":{"amount":"+0.9646219","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$8E9D3DB5-408D-41A7-8020-8DFABFE30AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ea1719e7801379a260a47a11b7d1c7efd06e3de","datavalue":{"value":{"entity-type":"item","numeric-id":3024777,"id":"Q3024777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32f8385b12ec8a5fd8a88e11f0c889f192aace5a","datavalue":{"value":{"amount":"+0.95191944","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$73C0E038-CC44-448B-9B44-295945C73C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2c9223ffc5159797589ed510c1676fd9bfaf7d","datavalue":{"value":{"entity-type":"item","numeric-id":1016540,"id":"Q1016540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61ab7c6fb9bb746e0ab505ce8a3519ec14e96bd2","datavalue":{"value":{"amount":"+0.94852316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$09F847E0-1556-4558-9A10-FB4D5A4A8212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aef05cca993358123fb2b8b3f1f17bbb151a3ab","datavalue":{"value":{"entity-type":"item","numeric-id":2934575,"id":"Q2934575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61ab7c6fb9bb746e0ab505ce8a3519ec14e96bd2","datavalue":{"value":{"amount":"+0.94852316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$DCA07D52-AA3E-4BE7-94AC-20AAEDDD9BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5184f9b7e9906d56962c7e728103bd32784e93f","datavalue":{"value":{"entity-type":"item","numeric-id":2326563,"id":"Q2326563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a4238d974996635bb9a1d32c7c0fc45816ceec1","datavalue":{"value":{"amount":"+0.9333344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$B0CF8077-04A1-4B43-9AE4-E01F50094572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b2f4f70aa9d0719bb9549ce6ab3a8ad15d9da47","datavalue":{"value":{"entity-type":"item","numeric-id":2300028,"id":"Q2300028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aeac450c2c18e1c6ec6afded0c9dfda87522109b","datavalue":{"value":{"amount":"+0.92085594","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$9184EEC0-CC87-4014-8AD9-433A7DA9FE4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e476e3e1b5eba1bfd08f12fb1aa6fb496e01dea","datavalue":{"value":{"entity-type":"item","numeric-id":6173263,"id":"Q6173263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"035e6f5899ab62c81225dbc677913900fa2e9ca9","datavalue":{"value":{"amount":"+0.91077524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$DBC4DC1B-5F9D-4811-9A92-1B618782A1AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6d6100188fb608bf9d5b0a397e153dd3c3c739a","datavalue":{"value":{"entity-type":"item","numeric-id":5390599,"id":"Q5390599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9279d2a52588366d81c32a9202f3f4430b1e7c5","datavalue":{"value":{"amount":"+0.910666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$9CCB2EF2-F3DB-4AB4-9DB9-9E4EC552AC0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59683c10fdc9a6ade234c179b2f16830366c34cc","datavalue":{"value":{"entity-type":"item","numeric-id":5854057,"id":"Q5854057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a7c06d5ed82c5766bdb9b4972859483367a28c7","datavalue":{"value":{"amount":"+0.90985584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762946$1B817DB6-CE04-4A3E-845B-E4AD9EB48854","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fault-tolerant geometric spanners","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fault-tolerant_geometric_spanners"}}}}}