{"entities":{"Q557839":{"pageid":559606,"ns":120,"title":"Item:Q557839","lastrevid":62730501,"modified":"2026-04-11T08:04:42Z","type":"item","id":"Q557839","labels":{"en":{"language":"en","value":"Embedding longest fault-free paths onto star graphs with more vertex faults"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184063"}},"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":"Q557839$D5822FC2-BC23-4C99-A174-35028D94CF72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bde4f841e73a1eedab27f206fffdc2b3425345c9","datavalue":{"value":{"text":"Embedding longest fault-free paths onto star graphs with more vertex faults","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q557839$BE83D647-71D2-4C23-BB75-4AFD9A2E0C7D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"413147a5fb6f0595386473f6e8bbebc6813adf2d","datavalue":{"value":"1104.68085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$147EEA04-F3DE-489A-9F8C-36E391FBF387","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebfe0ce9580b569ea92547b6dbfadeb499c82ae9","datavalue":{"value":{"entity-type":"item","numeric-id":269483,"id":"Q269483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$85DFD5A2-EA8C-4984-BC54-B1DB6C28E343","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$2BA3D98B-3D8D-4C23-B07E-ABC4C0B766F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q557839$3D7AAAD5-869E-49FF-BB85-B6969F2487AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef365c6022e0d27bfb76bd0ed2d6cea7d7f36ab8","datavalue":{"value":"An {\\(n\\)-dimensional star \\(S_n\\)} is a graph with vertex set equal to all the permutations of \\(n\\) numbers. Two vertices of \\(S_n\\) are adjacent if the corresponding permutations differ by a transposition involving their first elements. In particular, the graph \\(S_n\\) is \\((n-1)\\)-regular and bipartite. The author shows that for any set \\(W\\) of vertices of \\(S_n\\), \\(| W| \\leq n-3\\) and \\(n\\geq 4\\), and any two vertices \\(s\\) and \\(t\\) of \\(S_n\\), \\(s,t\\not\\in W\\), there exists a path between \\(s\\) and \\(t\\) of length at least \\(n!-2| W| -2\\) avoiding vertices contained in the set \\(W\\).  This improves previous results of \\textit{J.-H.~Chang, C.-S.~Shin} and \\textit{K.-Y.~Chwa} [IEICE Trans. Fund. E82-A~(9), 1953--1964 (1999)], \\textit{S.-Y. Hsieh, G.-H.~Chen} and \\textit{C.-W.~Ho} [Proc. Int. Conf. Parallel Process., 140--147 (1998)], and \\textit{S.-Y.~Hsieh, G.-H.~Chen} and \\textit{C.-W.~Ho} [Theor. Comput. Sci. 262, 215--227 (2001; Zbl 0983.68141)] by constant factors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q557839$214B3DE7-31D0-46F3-9445-060463FF0AA5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0c2dd2532a5942c0dd973983f0ad6a5a5c059eaa","datavalue":{"value":{"entity-type":"item","numeric-id":273100,"id":"Q273100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$5D18FAA8-7254-4A1F-8221-494483CF183A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$D84E71F9-4348-4CF6-AFBF-AB7FCDDF43C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$1B4348D2-F577-45A8-A218-4CE5FD80C3B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$F93A46D1-0FAE-4294-AA77-CDEF6BF57C9E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"364e6d9ac6d7ca3692e9f649486dfb8308bf49d9","datavalue":{"value":"2184063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$B0CCC4F2-DAE3-4500-B8C8-EAF31E61D508","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6309d07423c1bab1272e1bf84f1dd84da537362d","datavalue":{"value":"hypercubes","type":"string"},"datatype":"string"},"type":"statement","id":"Q557839$62566C84-3CBA-4760-8FA0-811A90F50190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3fd0a23781d6bc62cec83d8eeb639425e49870c","datavalue":{"value":"\\(n\\)-dimensional stars","type":"string"},"datatype":"string"},"type":"statement","id":"Q557839$EA9E742F-C929-4EC0-A1AA-23BE85584B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9cd193e049536e3b552b5ba57eb505b83c1222f8","datavalue":{"value":"fault-tolerant embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q557839$64D9BB37-81B7-4CD2-A24A-10A27E6271B8","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":"Q557839$9F35F11A-C5DF-423F-B71E-242427F4F52A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"591327af9e82fc878e29040c393c4726a75920b9","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2005.01.018","type":"string"},"datatype":"url"},"type":"statement","id":"Q557839$64C2B38C-8F6A-4390-BB8E-5DCD8C4229E2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0b1e6e6882a9ffe7188e421bd33ff851c1be9622","datavalue":{"value":"W2013044245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$3ACA6983-74E2-4F86-8588-7198FD95E638","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cede50f02af32002d10a5120078ff38111b0c90a","datavalue":{"value":{"entity-type":"item","numeric-id":3835424,"id":"Q3835424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$FECD8CCD-08F1-4017-B6DE-80DC486481FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"feafb260e5a4f6d2b4f38372c4443e885396b9c6","datavalue":{"value":{"entity-type":"item","numeric-id":4420948,"id":"Q4420948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$BE2B278E-9A51-4941-8204-E863F7B3B182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f5745193ef64cca31a81001237ff903195d4490","datavalue":{"value":{"entity-type":"item","numeric-id":4000490,"id":"Q4000490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$A92A3B25-5AC4-4D9F-A778-7CED9B9316E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c96776fc28c648791370f413c0f77449db861c3","datavalue":{"value":{"entity-type":"item","numeric-id":4761322,"id":"Q4761322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$1B7D42DC-BB55-48D2-925E-A951BB4EF10F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6526937e53eac2226f0d82dedb033bd61a1b7a7","datavalue":{"value":{"entity-type":"item","numeric-id":5958120,"id":"Q5958120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$D6C8D8B2-7427-46EE-A60A-9FCBC2A091A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b578d56855c1de2e2f897c61ed2ff7168e6c3325","datavalue":{"value":{"entity-type":"item","numeric-id":4002466,"id":"Q4002466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$B1D81D1B-92EC-40CB-AD12-F7BEC3BCD24E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47706281dbb7ee14e64aeb6018aa85776a816d98","datavalue":{"value":{"entity-type":"item","numeric-id":5375294,"id":"Q5375294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$C6E01E03-E467-48D2-8CAC-50529A097327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e593a8f52feb9c3a0fb6539e3c1f81b2a30681eb","datavalue":{"value":{"entity-type":"item","numeric-id":1309221,"id":"Q1309221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557839$69BDAC48-9F9A-4DB1-A852-BB9189B54F54","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2f83f6f44636bd08f0ccf4d3b9a596b37747ccdb","datavalue":{"value":"10.1016/J.TCS.2005.01.018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557839$05B657DA-4906-41EC-88CC-B5BA966CDF81","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f9f633f2f0ed4cc4698b9eb3cc9241a330f3dd1","datavalue":{"value":{"entity-type":"item","numeric-id":5958120,"id":"Q5958120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21ec8a57107721200d74dcb0aa40bf901f0dc1c7","datavalue":{"value":{"amount":"+0.9370027780532836","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":"Q557839$66099610-AAF9-4455-89BC-1562B67F7742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dde53e8887c7c4bce42bc6711af1621275b8768","datavalue":{"value":{"entity-type":"item","numeric-id":426437,"id":"Q426437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfc6b1baeff30d2c1fb1451c8010179cdc9a65b0","datavalue":{"value":{"amount":"+0.933867335319519","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":"Q557839$28420827-0686-4651-94DC-429ECACD554C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a5b4014fadf0fbef40d46dd8193e4998ffb5d91","datavalue":{"value":{"entity-type":"item","numeric-id":705576,"id":"Q705576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff78aee2f4e3d6530686826e18b93beeef89fe67","datavalue":{"value":{"amount":"+0.8912109136581421","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":"Q557839$FC385CAB-1338-47CC-AF1A-1377543E75FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"078b308df56c5c2adeea5ba1e2a026778fb9f8ee","datavalue":{"value":{"entity-type":"item","numeric-id":988635,"id":"Q988635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7213afe0dd288e03477426a637837d8772befc1","datavalue":{"value":{"amount":"+0.8805503249168396","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":"Q557839$0348BC42-1D9A-4B83-A255-82FE524FD75F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10a8377cf4a81a8d921b6791e6151982831a3305","datavalue":{"value":{"entity-type":"item","numeric-id":650935,"id":"Q650935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"898e85fc61fc8106047ab7fbbebaeadced5099e4","datavalue":{"value":{"amount":"+0.8347599506378174","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":"Q557839$B50A3737-26E9-4845-A04B-CE9BC27CA880","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Embedding longest fault-free paths onto star graphs with more vertex faults","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Embedding_longest_fault-free_paths_onto_star_graphs_with_more_vertex_faults"}}}}}