CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishA visit of a graph is a permutation of its vertices which establishes the order in which these are considered. In this paper we deal with the problem of determining visits that perform well in terms of accumulated edges, where at a given step of the visit an edge is accumulated iff both its endpoints have already been considered at that step. Several visits of this kind are here defined, the notion of strong and weak visitability presented, and the problem of deciding whether a graph can be correctly visited or not is considered. Such a problem is computationally hard in various versions. We then analyze necessary and suffcient conditions for graph visitability, characterize some a.e. visitable classes of graphs, describe polynomial-time algorithms to solve particular problem instances, and give heuristics and approximation algorithms for some intractable cases.
| Titolo: | How to Survive while Visiting a Graph | |
| Autori: | ||
| Data di pubblicazione: | 2000 | |
| Rivista: | ||
| Abstract: | A visit of a graph is a permutation of its vertices which establishes the order in which these are considered. In this paper we deal with the problem of determining visits that perform well in terms of accumulated edges, where at a given step of the visit an edge is accumulated iff both its endpoints have already been considered at that step. Several visits of this kind are here defined, the notion of strong and weak visitability presented, and the problem of deciding whether a graph can be correctly visited or not is considered. Such a problem is computationally hard in various versions. We then analyze necessary and suffcient conditions for graph visitability, characterize some a.e. visitable classes of graphs, describe polynomial-time algorithms to solve particular problem instances, and give heuristics and approximation algorithms for some intractable cases. | |
| Handle: | http://hdl.handle.net/20.500.12571/2883 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/20.500.12571/2883
Copyright © 2022