How to survive while visiting a graph
type: Item
instance of: scholarly article
title: How to survive while visiting a graph
zbMATH Open document ID: 0940.05062
DOI: 10.1016/S0166-218X(99)00139-0
author: Claudio Arbib
author: Enrico Nardelli
author: Michele Flammini
published in: Discrete Applied Mathematics
publication date: 2000-07-13T00:00:00Z
review text: 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.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1395017
zbMATH Keywords: visitability
zbMATH Keywords: accumulated edge
MaRDI profile type: Publication
cites work: Q3682518
cites work: A Sufficient Condition for Backtrack-Free Search
cites work: Q4198056
cites work: Q5572939
full work available at URL: s0166-218x(99)00139-0
OpenAlex ID: W2071028712
description: scientific article; zbMATH DE number 1395017