Spanning Properties of Theta-Theta Graphs
| Autor: | Mirela Damian, Dumitru V. Voicu |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Trapezoid graph 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Geometry 01 natural sciences 1-planar graph Metric dimension Combinatorics Indifference graph 010201 computation theory & mathematics Chordal graph 0202 electrical engineering electronic engineering information engineering Maximal independent set Theta graph Mathematics Minimum degree spanning tree |
| Zdroj: | Combinatorial Optimization and Applications ISBN: 9783319126906 COCOA |
| DOI: | 10.1007/978-3-319-12691-3_17 |
| Popis: | We study the spanning properties of Theta-Theta graphs. Similar in spirit with the Yao-Yao graphs, Theta-Theta graphs partition the space around each vertex into a set of \(k\) cones, for some fixed integer \(k > 1\), and select at most one edge per cone. The difference is in the way edges are selected. Yao-Yao graphs select an edge of minimum length, whereas Theta-Theta graphs select an edge of minimum orthogonal projection onto the cone bisector. It has been established that the Yao-Yao graphs with parameter \(k = 6k'\) have spanning ratio \(11.67\), for \(k' \ge 6\). In this paper we establish a first spanning ratio of \(7.82\) for Theta-Theta graphs, for the same values of \(k\). We also extend the class of Theta-Theta spanners with parameter \(6k'\), and establish a spanning ratio of \(16.76\) for \(k' \ge 5\). We surmise that these stronger results are mainly due to a tighter analysis in this paper, rather than Theta-Theta being superior to Yao-Yao as a spanner. We also show that the spanning ratio of Theta-Theta graphs decreases to \(4.64\) as \(k'\) increases to \(8\). These are the first results on the spanning properties of Theta-Theta graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|