Search results for " graph"
showing 10 items of 1277 documents
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
2006
A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…
Circular law for sparse random regular digraphs
2020
Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studyi…
Nonlocal discrete ∞-Poisson and Hamilton Jacobi equations
2015
In this paper we propose an adaptation of the ∞-Poisson equation on weighted graphs, and propose a finer expression of the ∞-Laplace operator with gradient terms on weighted graphs, by making the link with the biased version of the tug-of-war game. By using this formulation, we propose a hybrid ∞-Poisson Hamilton-Jacobi equation, and we show the link between this version of the ∞-Poisson equation and the adaptation of the eikonal equation on weighted graphs. Our motivation is to use this extension to compute distances on any discrete data that can be represented as a weighted graph. Through experiments and illustrations, we show that this formulation can be used in the resolution of many ap…
Estimation of Purkinje trees from electro-anatomical mapping of the left ventricle using minimal cost geodesics
2015
The electrical activation of the heart is a complex physiological process that is essential for the understanding of several cardiac dysfunctions, such as ventricular tachycardia (VT). Nowadays, patient-specific activation times on ventricular chambers can be estimated from electro-anatomical maps, providing crucial information to clinicians for guiding cardiac radio-frequency ablation treatment. However, some relevant electrical pathways such as those of the Purkinje system are very difficult to interpret from these maps due to sparsity of data and the limited spatial resolution of the system. We present here a novel method to estimate these fast electrical pathways from the local activati…
Hyperboloid and Parabolid in Orthogonal Axonometric
2012
This paper presents the issue of a long research on the representation of the complex surface in descriptive geometry. The ability to use the different techniques of representation aims to achieve results that you didn’t image before. In Palermo University, at the Engineering School, the researcher involved the study on the simplify of the so elaborated way to represent the geometry and its applications in architecture buildings and engineering implants. We just report below the application methods to represent two of the most used quadric surfaces in the practice of buildings. We are talking about Hyperboloid and Paraboloid quadric surface represented in axonometric projecting. This method…
Il Gran Caffè di Giuseppe Damiani Almeyda
2015
Il testo affronta lo studio di un’opera giovanile di Giuseppe Damiani Almeyda (1834-1911), figura di spicco del panorama architettonico in Sicilia tra la seconda metà dell’Ottocento ed i primi del Novecento. Il progetto del Gran Caffè, vincitore di prestigiosi riconoscimenti, anche se realizzato quando Damiani non era ancora trentenne, risulta molto maturo e segna una tappa importante nella formazione dell’architetto. Se ne ritroveranno richiami progettuali nel Politeama, edificio a cui il suo nome è legato, e in una grandiosa opera didattica, la Scuola Italiana di Architettura Civile, che, purtroppo, non è mai stata pubblicata. I disegni originali, a matita, inchiostro ed acquerello su car…
Space and Light, Towards an Interactive Simulation of Lighting
2003
International audience; Une image est une vue, à un instant donné, de l'équilibre lumineux présent dans une scène. Cet équilibre résulte d'un système complexe où l'énergie provenant des sources est re-distribuée dans l'espace par les matériaux appliqués aux formes. Si cet équilibre est perturbé par une modification des conditions lumineuses, l'image précédente n'est plus valide. En cela elle ne représente qu'un instant d'un lieu et non le lieu lui même. Nous proposons ici une approche pour la simulation interactive de l'éclairage dans une scène complexe. Une application à cette étude étant la production d'images vivantes et confondantes dans le cadre de la réalité augmentée.
Fusion of visual tools in virtual spaces
1996
Virtual space environment may be improved by combining it with graphical and visual tools. This paper analyses an integrated system able to merge fusion techniques, icons tools and a virtual space environment. A virtual space is characterised by a set of dynamic visual icons and by a heterogeneous virtual reality environment. Their integration is supported by virtual icon grammar (VIG) working on dynamic icons and virtual world. VIG allows to test the actions made by dynamic icons on the activated Virtual World metaphors at a time “t”, and a range of different transactions that place between user and VW(visual query, view and browse of under-world,...), moreover, user can define, modify and…
Curved Edge Routing
2001
We consider the problem of drawing a graph where edges are represented by smooth curves between the associated nodes. Previously curved edges were drawn as splines defined by carefully calculated control points. We present a completely different approach where finding an edge is reduced to solving a differential equation. This approach allows to represent the graph drawing aesthetics directly, even the most complex ones denoting the dependencies among the paths.
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.