𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coverings and Minors: Application to Local Computations in Graphs

✍ Scribed by Bruno Courcelle; Yves Métivier

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
398 KB
Volume
15
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Using the notion of covering, we prove that a minor-closed class of graphs cannot be recognized by local computations, except in a few special cases.

📜 SIMILAR VOLUMES

Graph models applied to specification, s
Graph models applied to specification, simulation, allocation, and scheduling of real-time computer vision applications
✍ F. Torres; F. A. Candelas; S. T. Puente; F. G. Ortiz 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

## Abstract This paper describes how graph models are applied to specification, simulation, allocation, and scheduling of real‐time computer vision applications. Furthermore, we present a new environment that allows the user to specify a Computer Vision program using graphic schemes and evaluates a

A probabilistic local majority polling g
A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
✍ Toshio Nakata; Hiroshi Imahayashi; Masafumi Yamashita 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB 👁 1 views

In this paper, we investigate a probabilistic local majority polling game on weighted directed graphs, keeping an application to the distributed agreement problem in mind. We formulate the game as a Markov chain, where an absorbing state corresponds to a system configuration that an agreement is ach

Magic labeling in graphs: Bounds, comple
Magic labeling in graphs: Bounds, complexity, and an application to a variant of TSP
✍ Kalantari, B.; Khosrovshahi, G. B. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 674 KB

Let G be an undirected graph with n vertices and m edges. A natural number A is said to be a magic labeling, positive magic /abe/ing, and fractional positive magic /abe/ing, if the edges can be labeled with nonnegative intqers, naturals, and rationals 2 1 , respectively, so that for each vertex the

An algorithm of propagation in weighted
An algorithm of propagation in weighted directed graphs with applications to economics and finance
✍ Mario Eboli 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

This paper puts forward an algorithm that computes the diffusion of events and actions across networks of economic agents, an algorithm that is applicable when such networks can be represented as weighted directed graphs. The functioning of the algorithm is shown in three applications. First, the al

Time-dependent local-density approximati
Time-dependent local-density approximation in real time: Application to conjugated molecules
✍ K. Yabana; G. F. Bertsch 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

The time-dependent local-density approximation TDLDA is applied to the optical response of conjugated carbon molecules in the energy range of 0᎐30 eV, with calculations given for carbon chains, polyenes, retinal, benzene, and C . The major 60 feature of the spectra, the collective ᎐ \* transition, i

Traps and Snares in Eigenvalue Calculati
Traps and Snares in Eigenvalue Calculations with Application to Pseudospectral Computations of Ocean Tides in a Basin Bounded by Meridians
✍ John P. Boyd 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 337 KB

the boundary conditions: the sines and cosines of a Fourier series for periodic problems, spherical harmonics for prob- We make several observations about eigenvalue problems using, as examples, Laplace's tidal equations and the differential equation