EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3741. On Minimum Euclidean Steiner Laman Graphs
Invited abstract in session TA-25: Applications of combinatorial optimization I, stream Combinatorial Optimization.
Tuesday, 8:30-10:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Naoki Katoh
|
| Graduate school of Inforrmation Science, University of Hyogo | |
| 2. | Hitomi Hayashi
|
| Graduate School of Information Science, University of Hyogo | |
| 3. | Yuya Higashikawa
|
| University of Hyogo | |
| 4. | Takashi Horiyama
|
| Faculty of Information Science and Technology, Hokkaido University | |
| 5. | Risa Ishikawa
|
| Information Science, University of Hyogo | |
| 6. | Yuki Kawakami
|
| Hokkaido University | |
| 7. | Yuki Kobayashi
|
| Graduate School of Engineering, Osaka Metropolitan University | |
| 8. | Ayano Nishii
|
| Graduate School of Information Science, University of Hyogo | |
| 9. | Junichi Teruyama
|
| University of Hyogo | |
| 10. | Yinfeng Xu
|
| School of management, Xi'anjiaotong University | |
| 11. | Azusa Yamamoto
|
| Graduate School of Information Science, University of Hyogo |
Abstract
An Euclidean Laman graph is a geometric graph on n vertices in the
plane with exactly 2n − 3 edges such that, for all k > 1, every
k-vertex subgraph has at most 2k − 3 edges. In this study, we
introduce a variant of the well-known Euclidean Steiner tree problem,
say the Euclidean Steiner Laman graph problem (ESL for short). Given a
point set P in the plane, the goal is to find an Euclidean Laman graph
of minimum total length such that any point in P is contained as one
of its vertices. We also consider the problem of finding a plane
(i.e., non-crossing) solution under the same setting, say the
Euclidean Steiner plane Laman graph problem (ESPL for short).
First, we prove an optimal solution for ESL has no crossing, i.e., an optimal solution for ESPL is also optimal for ESL. Then, we design a polynomial time approximation algorithm that outputs a plane Laman graph and guarantees an approximation ratio at most asymptotically 1.5+ Ɛ with an arbitrarily positive Ɛ.
Keywords
- Combinatorial Optimization
- Network Design
- Graphs and Networks
Status: accepted
Back to the list of papers