Proximity graphs inside large weighted graphs
| Autor: | Bernardo M. Ábrego, Vera Sacristán, Maria Saumell, David Flores-Peñaloza, Ruy Fabila-Monroy, Henk Meijer, Ferran Hurtado, Silvia Fernández-Merchant |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Clique-sum Grafs Teoria de Computer Networks and Communications Voronoi polygons Trapezoid graph Algorismes Metric dimension Graph theory Combinatorics Indifference graph Pathwidth Hardware and Architecture Chordal graph Neighborhoods Voronoi Polígons de Maximal independent set Cograph Algorithms Software MathematicsofComputing_DISCRETEMATHEMATICS Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] Information Systems Mathematics |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| ISSN: | 0028-3045 |
| DOI: | 10.1002/net.21464 |
| Popis: | Given a weighted graph G = (V,E) and a subset U of V, we define several graphs with vertex set U in which two vertices are adjacent if they satisfy a specific proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013 © 2013 Wiley Periodicals, Inc. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text