1,721,050 research outputs found
Characterizations of Graphs with Stretch Number less than 2
No full textGiven a simple and finite connected graph G, the distance d(u,v) is the length of the shortest (u,v)-path in G. Cicerone and Di Stefano [Graphs with bounded induced distance, Discrete Applied Mathematics 108 (2001), pp. 3–21] introduced and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. In this paper we make a step forward in the study of such graphs by providing characterizations for k-distance-hereditary graphs, k>2, in terms of both forbidden subgraphs and cycle-chord conditions. Such results lead to a polynomial-time recognition algorithm
Efficient estimation of qualitative topological relations based on the weighted walkthroughs model
No full textWeighted walkthroughs are a quantitative model for representing the spatial relation between two raster features in image databases. In this paper, we establish a correspondence between the weighted walkthroughs and qualitative models for spatial reasoning. We provide rules for estimating qualitative geometric properties and topological relations from the quantitative data that are computed for each pair of pixel sets. The approach has been tested through experiments with raster regions
Cardinal directions between spatial objects: the pairwise-consistency problem
No full textThe paper formalizes an open-problem (called by the authors the pairwise-consistency problem) which is relevant in the context of cardinal directions among extended objects, proposes an efficient algorithmic solution for it, discusses the implementation of the algorithm and briefly reports the numerical results obtained by running the code
Graph classes between parity and distance-hereditary graphs
No full textSeveral graph problems (e.g., steiner tree, connected domination, hamiltonian
path, and isomorphism problem), which can be solved in polynomial time for
distance-hereditary graphs, are NP-complete or have unknown complexity for parity
graphs. Moreover, the metric characterizations of these two graph classes suggest
an excessive gap between them. We introduce a family of classes forming an
infinite lattice with respect to inclusion, whose extreme points are exactly parity and
distance-hereditary classes. Then, we characterize these classes using Cunningham decomposition and use such a characterization in order to show efficient algorithms for the recognition and isomorphism problems
Networks with small stretch number
No full textAbstractIn a previous work, the authors introduced the class of graphs with bounded induced distance of order k (BID(k) for short), to model non-reliable interconnection networks. A network modeled as a graph in BID(k) can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is at most k times the distance in the non-faulty graph. The smallest k such that G∈BID(k) is called stretch number of G. We show an odd characteristic of the stretch numbers: every rational number greater or equal 2 is a stretch number, but only discrete values are admissible for smaller stretch numbers. Moreover, we give a new characterization of classes BID(2−1/i), i⩾1, based on forbidden induced subgraphs. By using this characterization, we provide a polynomial time recognition algorithm for graphs belonging to these classes, while the general recognition problem is Co-NP-complete
Cardinal directions between spatial objects: the pairwise-consistency problem (extended abstract)
No full textThe paper formalizes an open-problem (called by the authors the pairwise-consistency problem) which is relevant in the context of cardinal directions among extended objects, proposes an efficient algorithmic solution for it, discusses the implementation of
the algorithm and briefly reports the numerical results obtained by running the code
A structured methodology for designing distributed algorithms for mobile entities
No full textFollowing the wide investigation in distributed computing issues by mobile entities of the last two decades, we consider the need of a structured methodology to tackle the arisen problems. The aim is to simplify both the design of the resolution algorithms and the writing of the required correctness proofs. We would encourage the usage of a common framework in order to help both algorithm designers and reviewers in the intricate work of delivering and analyzing the proposed resolution strategies.
We demonstrate the effectiveness and usefulness of the new methodology by highlighting various peculiarities arising in different scenarios. In particular, we consider two different tasks for asynchronous entities moving in the Euclidean plane and in graphs, respectively. We show how two resolution strategies have been designed by following the accurate guide dictated by the methodology. Furthermore, we also show how the corresponding correctness proofs are obtained
Networks with Small Stretch Number
No full textIn a previous work, the authors introduced the class of "graphs
with bounded induced distance of order k", (BID(k) for short) to
model non-reliable interconnection networks. A network modeled as a
graph in BID(k) can be characterized as follows: if some nodes have
failed, as long as two nodes remain connected, the distance between
these nodes in the faulty graph is at most k times the distance in
the non-faulty graph. The smallest k such that G is in BID(k) is
called "stretch number" of G. In this paper we give new
characterization, algorithmic, and existence results about graphs with
small stretch number
Interacting with Geographic Databases: a Focus+Context Approach
No full textWe present results on the design of a visual interaction environment
for Geographic Information Systems, with focus on support of
navigational tasks. We envision an exploration of the database where,
starting from an abstract view, more and more detailed information is
successively disclosed on demand, and visualized in a fish-eye view
fashion. The interaction process is a sequence of views on the
database, each displayed by a map in which topological properties are
preserved. An efficient navigation requires the adoption of
topological invariants for representing such partitions. These
invariants might be computed from scratch at each step by using
algorithms known in the literature. Since each interaction step
modifies only a portion of the current topological invariant, we
propose an efficient {\em incremental approach}, to update the current
topological invariant by exploiting knowledge coming from previous
steps, instead of recomputing always everything from scratch. This
approach is mainly based on the formalization of the interaction
process starting from the notion of "nested partition" of a
spatial databas
- …
