×

Found 928 Documents (Results 1–100)

Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs. (English) Zbl 07728665

Bagchi, Amitabha (ed.) et al., Algorithms and discrete applied mathematics. 9th international conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13947, 219-230 (2023).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

P versus NPC: minimum Steiner trees in convex split graphs. (English) Zbl 07683167

Balachandran, Niranjan (ed.) et al., Algorithms and discrete applied mathematics. 8th international conference, CALDAM 2022, Puducherry, India, February 10–12, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13179, 115-126 (2022).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage. (English) Zbl 07556576

Mutzel, Petra (ed.) et al., WALCOM: algorithms and computation. 16th international conference and workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13174, 251-262 (2022).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Three is enough for Steiner trees. (English) Zbl 07700587

Coudert, David (ed.) et al., 19th international symposium on experimental algorithms, SEA 2021, Nice, France, June 7–9, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 190, Article 5, 15 p. (2021).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Approximation algorithms for priority Steiner tree problems. (English) Zbl 07670456

Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 112-123 (2021).
MSC:  68Rxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

On the terminal connection problem. (English) Zbl 1490.68150

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 278-292 (2021).
MSC:  68R10 68Q17 68Q25
PDF BibTeX XML Cite
Full Text: DOI

Implications, conflicts, and reductions for Steiner trees. (English) Zbl 1483.90144

Singh, Mohit (ed.) et al., Integer programming and combinatorial optimization. 22nd international conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12707, 473-487 (2021).
MSC:  90C27
PDF BibTeX XML Cite
Full Text: DOI

Kruskal-based approximation algorithm for the multi-level Steiner tree problem. (English) Zbl 07651143

Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 4, 21 p. (2020).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

A 2-approximation for the \(k\)-prize-collecting Steiner tree problem. (English) Zbl 07600766

Kohayakawa, Yoshiharu (ed.) et al., Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12118, 76-88 (2020).
MSC:  68Qxx 68Rxx 68Wxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Computing a minimum-cost \(k\)-hop Steiner tree in tree-like metrics. (English) Zbl 07559389

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 18, 15 p. (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\). (English) Zbl 1482.68255

Zhang, Zhao (ed.) et al., Algorithmic aspects in information and management. 14th international conference, AAIM 2020, Jinhua, China, August 10–12, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12290, 49-61 (2020).
PDF BibTeX XML Cite
Full Text: DOI

Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. (English) Zbl 07298290

Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 815-825 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Reconfiguration of minimum Steiner trees via vertex exchanges. (English) Zbl 07561723

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 79, 11 p. (2019).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Geometric multicut. (English) Zbl 07561502

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 9, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration. (English) Zbl 07378612

Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 26, 15 p. (2019).
MSC:  68R10 68Q27 68W40
PDF BibTeX XML Cite
Full Text: DOI

Graph simplification for infrastructure network design. (English) Zbl 1435.68246

Li, Yingshu (ed.) et al., Combinatorial optimization and applications. 13th international conference, COCOA 2019, Xiamen, China, December 13–15, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11949, 576-589 (2019).
MSC:  68R10 68M10
PDF BibTeX XML Cite
Full Text: DOI Link

Travelling on graphs with small highway dimension. (English) Zbl 07173299

Sau, Ignasi (ed.) et al., Graph-theoretic concepts in computer science. 45th international workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019. Revised papers. Cham: Springer. Lect. Notes Comput. Sci. 11789, 175-189 (2019).
MSC:  68R10
PDF BibTeX XML Cite
Full Text: DOI arXiv

The 4-Steiner Root problem. (English) Zbl 07173287

Sau, Ignasi (ed.) et al., Graph-theoretic concepts in computer science. 45th international workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019. Revised papers. Cham: Springer. Lect. Notes Comput. Sci. 11789, 14-26 (2019).
MSC:  68R10
PDF BibTeX XML Cite
Full Text: DOI HAL

\(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. (English) Zbl 1433.68614

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 253-264 (2019).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference

all top 3

Software