{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1962049","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1962049","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1962049","kernelVersion":"v1","immutable":true,"modified":"2026-01-01T18:17:03Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1962049","name":"How to survive while visiting a graph","headline":"How to survive while visiting a graph","description":"scientific article; zbMATH DE number 1395017","url":"https://portal.mardi4nfdi.de/entity/Q1962049","datePublished":"2000-07-13","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q429691"},{"@id":"https://portal.mardi4nfdi.de/entity/Q287113"},{"@id":"https://portal.mardi4nfdi.de/entity/Q237650"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q96294"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/S0166-218X(99)00139-0","url":"https://doi.org/10.1016/S0166-218X(99)00139-0"},"sameAs":["https://doi.org/10.1016/S0166-218X(99)00139-0"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3682518"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3933756"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4198056"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5572939"}]},"provenance":{"prov:generatedAtTime":"2026-01-01T18:17:03Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}