{"entities":{"Q1962049":{"pageid":1972791,"ns":120,"title":"Item:Q1962049","lastrevid":47437291,"modified":"2026-01-01T18:17:03Z","type":"item","id":"Q1962049","labels":{"en":{"language":"en","value":"How to survive while visiting a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395017"}},"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":"Q1962049$3C55211B-B723-4CD9-BE1D-45876F939909","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8b16b8154198b40bc690ce957d65279633789b4","datavalue":{"value":{"text":"How to survive while visiting a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962049$BD984CC6-B5B7-49E2-BADC-A7795ABB29B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7d56fd8e3fc1e30cf6df1df1485e66df3c4412e","datavalue":{"value":"0940.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962049$ACBC004E-812E-4178-ACAC-8C9E0A1C5740","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"007b7bd161475a758ec906dfdfb7ec06bd1586a4","datavalue":{"value":"10.1016/S0166-218X(99)00139-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962049$8D764E4E-EBF2-415B-A8B9-0994AF29C7A3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"268c86183b2f5c73b7d063861a79c1303bb9cf99","datavalue":{"value":{"entity-type":"item","numeric-id":429691,"id":"Q429691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$B4EA247A-605B-4681-9C98-8751DA238DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"45074c0b16e92f4eda81549d14b600e55a34dfff","datavalue":{"value":{"entity-type":"item","numeric-id":287113,"id":"Q287113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$32B36340-F5AA-40E1-ADA5-D9F95CE03DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e637f17d951cabcf68452f82dad28cfc2f937a4d","datavalue":{"value":{"entity-type":"item","numeric-id":237650,"id":"Q237650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$32E14E2F-9819-4933-9187-7F232E8757C1","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":"Q1962049$F6EBCE02-9D34-4192-842B-A5880A816BE9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4dc3d990a0a8b8ad0b1a8a62e538a71a4d2cf07","datavalue":{"value":{"time":"+2000-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962049$D018E4D4-90BE-41CF-8681-691795C8A676","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e292fe10c777f5acb2d82df81228cf0ab68bb8cc","datavalue":{"value":"Let \\(G = (V, E)\\) be a graph with \\(n\\) vertices, and let \\(\\sigma : V \\rightarrow \\{1, \\ldots, n\\}\\) be a bijection. For \\(1 \\leq i \\leq n\\), the set \\(E_i(\\sigma)\\) of edges accumulated by visit \\(\\sigma\\) from step \\(1\\) to step \\(i\\) is the edge set of the subgraph induced by \\(\\{v \\in V : \\sigma(v) \\leq i\\}\\). Given a vector \\(d =(d_1, \\ldots, d_{n-1})\\), such a bijection \\(\\sigma\\) is a strong \\(d\\)-visit of \\(G\\) if \\(|E_{i+1}(\\sigma) - E_i(\\sigma)|\\geq d_i\\) for \\(1\\leq i\\leq n\\), and \\(\\sigma\\) is a weak \\(d\\)-visit of \\(G\\) if \\(|E_{i+1}(\\sigma)|\\geq \\sum_{j=1}^i d_j\\) for \\(1\\leq i\\leq n\\). The authors point out that the problem whether a graph admits a strong (resp. a weak) \\(d\\)-visit for a given vector \\(d\\) is NP-complete.    For a given positive integer \\(k\\), if the vector \\(d\\) satisfies \\(d_j=0\\) \\((1\\leq j < k)\\) and \\(d_j=k\\) \\((k\\leq i < n)\\) then a strong/weak \\(d\\)-visit of \\(G\\) is also called strong/weak \\(k\\)-visit. Among others, the authors prove, given a graph \\(G\\) with \\(n\\) vertices, an integer \\(k >0\\), and a set of \\(k\\) vertices \\(\\{v_1, \\dots, v_k\\}\\), that (1) there exists an \\(O(n^2)\\)-time algorithm that finds a strong \\(k\\)-visit \\(\\sigma\\) of \\(G\\) with \\(\\sigma(v_i)=i\\) \\((1\\leq i\\leq k)\\), if one exists, and returns a negative answer otherwise; in particular, a strong \\(k\\)-visit (if any at all) can be found in \\(O(n^{k+2})\\) time, and (2) deciding whether \\(G\\) admits or does not admit a weak \\(k\\)-visit \\(\\sigma\\) with \\(\\sigma(v_i)=i\\) \\((1\\leq i\\leq k)\\) is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962049$57641B9C-68E7-47DF-A800-F75C8C13DD55","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$B9FCF866-6E40-41C1-88C0-53AFC71431E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962049$12770D44-75AA-4AFF-B14C-5A9EF2366C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962049$D2527D4E-32AA-4351-A04F-15AF4A69097C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8de9260ffbbb66e36b98d96f233eec3119896112","datavalue":{"value":"1395017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962049$43304D8E-751E-4CD9-BE5E-5FC25F8B70BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53140b57d65e89bfc5b6ca08da72d40ba592f449","datavalue":{"value":"visitability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962049$C01D9467-757D-4D1A-85C8-732ED5B329A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a055ad3cbd0c82ba923164a2dc71c2cd5adcd58","datavalue":{"value":"accumulated edge","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962049$C49967E3-9E24-439B-AB83-FCD2FC0AC0DC","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":"Q1962049$A3A05C23-6C71-4ED0-B68D-261050836EC3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$E109B5E6-3C70-4B1E-9CD8-A92AE01B2887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1958ff7e040b608ab81be40fc268247c86c0f1","datavalue":{"value":{"entity-type":"item","numeric-id":3933756,"id":"Q3933756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$0EDA86AA-BD03-4694-BE81-29403059AC95","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":"Q1962049$75432D62-D344-4DB2-B758-028BBED40AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962049$FAAF0FFF-D45D-4591-BD8B-88F9C30DF2D0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a332faad20c2a5d347fff2cdc9d86502c246f9e1","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00139-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1962049$35E99C37-D563-4C7F-BB68-EB7A0034FE14","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"042746948d3ee32faeab7b32f039ebe9d05a1a20","datavalue":{"value":"W2071028712","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962049$DD0DE544-3AB4-4412-8C85-F5E23EEB93F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"086cbb348ac7ef6850c07333bf3327a72b2dca68","datavalue":{"value":{"entity-type":"item","numeric-id":3691758,"id":"Q3691758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f785548dff725a8def3cc27285dd06c6b99c207e","datavalue":{"value":{"amount":"+0.6907916069030762","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":"Q1962049$69E07E12-012B-4DE2-80BD-B2014AC94E7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff4b5b3d66dfd5a70387de91c90102fa5d433d54","datavalue":{"value":{"entity-type":"item","numeric-id":1265251,"id":"Q1265251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"930050bab34e50b19411f74f790f0229f46ecb42","datavalue":{"value":{"amount":"+0.6809611916542053","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":"Q1962049$50D1E43E-ABAE-4551-AB5D-843D2E0A2A65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1415d9b97c1bec522844069779009e41c3bab3a","datavalue":{"value":{"entity-type":"item","numeric-id":3789367,"id":"Q3789367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bda5bf35b1aa5aac15c4ac7c6b3639d081f7bd8b","datavalue":{"value":{"amount":"+0.679179847240448","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":"Q1962049$576877C2-36A8-425A-927B-93FCB0AFC1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5d3f858fdf7dcbdcc3f1afdbec0e812ea5b8100","datavalue":{"value":{"entity-type":"item","numeric-id":997060,"id":"Q997060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaf750bf6b2500255849afd4f61e21ba0855d2a8","datavalue":{"value":{"amount":"+0.6752452254295349","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":"Q1962049$6E67AAE8-07E2-4C89-BDB8-DA08EA649CBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7250d87628500fd8999cb5dbb3f70a60f79bbc14","datavalue":{"value":{"entity-type":"item","numeric-id":3777477,"id":"Q3777477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d72044cfd5963c0f4b39798efff5f783ff669e5","datavalue":{"value":{"amount":"+0.6728546619415283","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":"Q1962049$4EE7D77C-DDC7-412B-A027-D61BFC558A14","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962049","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962049"}}}}}