PTAS for Steiner Tree on Map Graphs

Jarosław Byrka; Mateusz Lewandowski; Syed Mohammad Meesum; Joachim Spoerhase; Sumedha Uniyal

doi:10.1007/978-3-030-61792-9_1

PTAS for Steiner Tree on Map Graphs

Jarosław Byrka, Mateusz Lewandowski^*, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal

^*Tämän työn vastaava kirjoittaja

University of Wrocław

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

Abstrakti

We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

Alkuperäiskieli	Englanti
Otsikko	LATIN 2020
Alaotsikko	Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings
Toimittajat	Yoshiharu Kohayakawa, Flávio Keidi Miyazawa
Kustantaja	SPRINGER
Sivut	3-14
Sivumäärä	12
ISBN (painettu)	9783030617912
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-030-61792-9_1
Tila	Julkaistu - 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	Latin American Symposium on Theoretical Informatics - Sao Paulo, Brasilia Kesto: 5 tammik. 2021 → 8 tammik. 2021 Konferenssinumero: 14

Julkaisusarja

Nimi	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Kustantaja	Springer
Vuosikerta	12118 LNCS
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	Latin American Symposium on Theoretical Informatics
Lyhennettä	LATIN
Maa/Alue	Brasilia
Kaupunki	Sao Paulo
Ajanjakso	05/01/2021 → 08/01/2021

Pääsy asiakirjaan

10.1007/978-3-030-61792-9_1

https://arxiv.org/abs/1912.00717

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

Byrka, J., Lewandowski, M., Meesum, S. M., Spoerhase, J., & Uniyal, S. (2020). PTAS for Steiner Tree on Map Graphs. teoksessa Y. Kohayakawa, & F. K. Miyazawa (Toimittajat), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings (Sivut 3-14). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 12118 LNCS). SPRINGER. https://doi.org/10.1007/978-3-030-61792-9_1

Byrka, Jarosław ; Lewandowski, Mateusz ; Meesum, Syed Mohammad et al. / PTAS for Steiner Tree on Map Graphs. LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Toimittaja / Yoshiharu Kohayakawa ; Flávio Keidi Miyazawa. SPRINGER, 2020. Sivut 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0aad7f5b46114016a73d197c01148003,

title = "PTAS for Steiner Tree on Map Graphs",

abstract = "We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.",

author = "Jaros{\l}aw Byrka and Mateusz Lewandowski and Meesum, {Syed Mohammad} and Joachim Spoerhase and Sumedha Uniyal",

year = "2020",

doi = "10.1007/978-3-030-61792-9_1",

language = "English",

isbn = "9783030617912",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "SPRINGER",

pages = "3--14",

editor = "Yoshiharu Kohayakawa and Miyazawa, {Fl{\'a}vio Keidi}",

booktitle = "LATIN 2020",

address = "Germany",

note = "Latin American Symposium on Theoretical Informatics, LATIN ; Conference date: 05-01-2021 Through 08-01-2021",

}

Byrka, J, Lewandowski, M, Meesum, SM, Spoerhase, J & Uniyal, S 2020, PTAS for Steiner Tree on Map Graphs. julkaisussa Y Kohayakawa & FK Miyazawa (toim), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vuosikerta 12118 LNCS, SPRINGER, Sivut 3-14, Latin American Symposium on Theoretical Informatics, Sao Paulo, Brasilia, 05/01/2021. https://doi.org/10.1007/978-3-030-61792-9_1

PTAS for Steiner Tree on Map Graphs. / Byrka, Jarosław; Lewandowski, Mateusz; Meesum, Syed Mohammad et al.

LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. toim. / Yoshiharu Kohayakawa; Flávio Keidi Miyazawa. SPRINGER, 2020. s. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 12118 LNCS).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

TY - GEN

T1 - PTAS for Steiner Tree on Map Graphs

AU - Byrka, Jarosław

AU - Lewandowski, Mateusz

AU - Meesum, Syed Mohammad

AU - Spoerhase, Joachim

AU - Uniyal, Sumedha

N1 - Conference code: 14

PY - 2020

Y1 - 2020

N2 - We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

AB - We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

UR - http://www.scopus.com/inward/record.url?scp=85097715149&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-61792-9_1

DO - 10.1007/978-3-030-61792-9_1

M3 - Conference contribution

AN - SCOPUS:85097715149

SN - 9783030617912

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 14

BT - LATIN 2020

A2 - Kohayakawa, Yoshiharu

A2 - Miyazawa, Flávio Keidi

PB - SPRINGER

T2 - Latin American Symposium on Theoretical Informatics

Y2 - 5 January 2021 through 8 January 2021

ER -

Byrka J, Lewandowski M, Meesum SM, Spoerhase J, Uniyal S. PTAS for Steiner Tree on Map Graphs. julkaisussa Kohayakawa Y, Miyazawa FK, toimittajat, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. SPRINGER. 2020. s. 3-14. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-61792-9_1

PTAS for Steiner Tree on Map Graphs

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä