A 2-Approximation for the k-Prize-Collecting Steiner Tree Problem (English)
- New search for: Pedrosa, Lehilton L. C.
- Further information on Pedrosa, Lehilton L. C.:
- https://orcid.org/http://orcid.org/0000-0003-1001-082X
- New search for: Rosado, Hugo K. K.
- Further information on Rosado, Hugo K. K.:
- https://orcid.org/http://orcid.org/0000-0002-8881-9699
- New search for: Kohayakawa, Yoshiharu
- Further information on Kohayakawa, Yoshiharu:
- https://orcid.org/https://orcid.org/0000-0001-7841-157X
- New search for: Miyazawa, Flávio Keidi
- Further information on Miyazawa, Flávio Keidi:
- https://orcid.org/https://orcid.org/0000-0002-1067-6421
- New search for: Pedrosa, Lehilton L. C.
- Further information on Pedrosa, Lehilton L. C.:
- https://orcid.org/http://orcid.org/0000-0003-1001-082X
- New search for: Rosado, Hugo K. K.
- Further information on Rosado, Hugo K. K.:
- https://orcid.org/http://orcid.org/0000-0002-8881-9699
In:
LATIN 2020: Theoretical Informatics
: 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings
;
Chapter: 7
;
76-88
;
2020
- Article/Chapter (Book) / Electronic Resource
-
Title:A 2-Approximation for the k-Prize-Collecting Steiner Tree Problem
-
Additional title:Lect.Notes Computer
-
Contributors:Kohayakawa, Yoshiharu ( editor ) / Miyazawa, Flávio Keidi ( editor ) / Pedrosa, Lehilton L. C. ( author ) / Rosado, Hugo K. K. ( author )
-
Conference:Latin American Symposium on Theoretical Informatics ; 2021 ; Sao Paulo, Brazil
-
Published in:LATIN 2020: Theoretical Informatics : 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings ; Chapter: 7 ; 76-88Lecture Notes in Computer Science ; 12118 ; 76-88
-
Publisher:
- New search for: Springer International Publishing
-
Place of publication:Cham
-
Publication date:2020-12-03
-
Size:13 pages
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Article/Chapter (Book)
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Source:
Table of contents eBook
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
PTAS for Steiner Tree on Map GraphsByrka, Jarosław / Lewandowski, Mateusz / Meesum, Syed Mohammad / Spoerhase, Joachim / Uniyal, Sumedha et al. | 2020
- 2
-
Near-Linear Time Algorithm for Approximate Minimum Degree Spanning TreesDuan, Ran / He, Haoqing / Zhang, Tianyi et al. | 2020
- 3
-
Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-RelaxationsElbassioni, Khaled et al. | 2020
- 4
-
Scheduling on Hybrid Platforms: Improved Approximability WindowFagnon, Vincent / Kacem, Imed / Lucarelli, Giorgio / Simon, Bertrand et al. | 2020
- 5
-
Leafy Spanning Arborescences in DAGsFernandes, Cristina G. / Lintzmayer, Carla N. et al. | 2020
- 6
-
Approximating Routing and Connectivity Problems with Multiple DistancesPedrosa, Lehilton L. C. / Quesquén, Greis Y. O. et al. | 2020
- 7
-
A 2-Approximation for the k-Prize-Collecting Steiner Tree ProblemPedrosa, Lehilton L. C. / Rosado, Hugo K. K. et al. | 2020
- 8
-
Maximizing Happiness in Graphs of Bounded Clique-WidthBliznets, Ivan / Sagunov, Danil et al. | 2020
- 9
-
Graph Hamiltonicity Parameterized by Proper Interval Deletion SetGolovach, Petr A. / Krithika, R. / Sahu, Abhishek / Saurabh, Saket / Zehavi, Meirav et al. | 2020
- 10
-
Graph Square Roots of Small Distance from Degree One GraphsGolovach, Petr A. / Lima, Paloma T. / Papadopoulos, Charis et al. | 2020
- 11
-
Structural Parameterizations for Equitable ColoringGomes, Guilherme C. M. / Guedes, Matheus R. / dos Santos, Vinicius F. et al. | 2020
- 12
-
Dynamically Optimal Self-adjusting Single-Source Tree NetworksAvin, Chen / Mondal, Kaushik / Schmid, Stefan et al. | 2020
- 13
-
Batched Predecessor and Sorting with Size-Priced Information in External MemoryBender, Michael A. / Goswami, Mayank / Medjedovic, Dzejla / Montes, Pablo / Tsichlas, Kostas et al. | 2020
- 14
-
Probabilistically Faulty Searching on a Half-LineBonato, Anthony / Georgiou, Konstantinos / MacRury, Calum / Prałat, Paweł et al. | 2020
- 15
-
Query Minimization Under Stochastic UncertaintyChaplick, Steven / Halldórsson, Magnús M. / de Lima, Murilo S. / Tonoyan, Tigran et al. | 2020
- 16
-
Suffix Trees, DAWGs and CDAWGs for Forward and Backward TriesInenaga, Shunsuke et al. | 2020
- 17
-
Towards a Definitive Measure of RepetitivenessKociumaka, Tomasz / Navarro, Gonzalo / Prezza, Nicola et al. | 2020
- 18
-
Flips in Higher Order Delaunay TriangulationsArseneva, Elena / Bose, Prosenjit / Cano, Pilar / Silveira, Rodrigo I. et al. | 2020
- 19
-
An \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (n^3)$$\end{document} Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-Dimensional Polyhedral StructuresBauernöppel, Frank / Maheshwari, Anil / Sack, Jörg-Rüdiger et al. | 2020
- 20
-
Computing Balanced Convex Partitions of LinesBereg, Sergey et al. | 2020
- 21
-
Ordered Strip PackingBuchin, K. / Kosolobov, D. / Sonke, W. / Speckmann, B. / Verbeek, K. et al. | 2020
- 22
-
Shortest Rectilinear Path Queries to Rectangles in a Rectangular DomainKim, Mincheol / Yoon, Sang Duk / Ahn, Hee-Kap et al. | 2020
- 23
-
Farthest Color Voronoi Diagrams: Complexity and AlgorithmsMantas, Ioannis / Papadopoulou, Evanthia / Sacristán, Vera / Silveira, Rodrigo I. et al. | 2020
- 24
-
Rectilinear Convex Hull of Points in 3DPérez-Lantero, Pablo / Seara, Carlos / Urrutia, Jorge et al. | 2020
- 25
-
Monotone Circuit Lower Bounds from Robust SunflowersCavalar, Bruno Pasqualotto / Kumar, Mrinal / Rossman, Benjamin et al. | 2020
- 26
-
Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive FunctionsChaubal, Siddhesh / Gál, Anna et al. | 2020
- 27
-
Sherali-Adams and the Binary Encoding of Combinatorial PrinciplesDantchev, Stefan / Ghani, Abdul / Martin, Barnaby et al. | 2020
- 28
-
Hardness of Variants of the Graph Coloring GameMarcilon, Thiago / Martins, Nicolas / Sampaio, Rudini et al. | 2020
- 29
-
Tractable Unordered 3-CNF GamesRahman, Md Lutfar / Watson, Thomas et al. | 2020
- 30
-
Lower Bounds for Testing Complete Positivity and Quantum SeparabilityBădescu, Costin / O’Donnell, Ryan et al. | 2020
- 31
-
Exponential-Time Quantum Algorithms for Graph Coloring ProblemsShimizu, Kazuya / Mori, Ryuhei et al. | 2020
- 32
-
On Symmetry and Initialization for Neural NetworksNachum, Ido / Yehudayoff, Amir et al. | 2020
- 33
-
How to Color a French FlagAncona, Bertie / Bajwa, Ayesha / Lynch, Nancy / Mallmann-Trenn, Frederik et al. | 2020
- 34
-
Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding ModelPchelina, Daria / Schabanel, Nicolas / Seki, Shinnosuke / Ubukata, Yuki et al. | 2020
- 35
-
Transmitting once to Elect a Leader on Wireless NetworksAndriambolamalala, Ny Aina / Ravelomanana, Vlady et al. | 2020
- 36
-
Asymptotics for Push on the Complete GraphDaknama, Rami / Panagiotou, Konstantinos / Reisser, Simon et al. | 2020
- 37
-
The Hardness of Sampling Connected SubgraphsRead-McFarland, Andrew / Štefankovič, Daniel et al. | 2020
- 38
-
Lower Bounds for Max-Cut via Semidefinite ProgrammingCarlson, Charles / Kolla, Alexandra / Li, Ray / Mani, Nitya / Sudakov, Benny / Trevisan, Luca et al. | 2020
- 39
-
Quasi-Random Words and Limits of Word SequencesHàn, Hiệp / Kiwi, Marcos / Pavez-Signé, Matías et al. | 2020
- 40
-
Thresholds in the Lattice of Subspaces of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {F}_q^n$$\end{document}Rossman, Benjamin et al. | 2020
- 41
-
On Minimal-Perimeter Lattice AnimalsBarequet, Gill / Ben-Shachar, Gil et al. | 2020
- 42
-
Improved Upper Bounds on the Growth Constants of Polyominoes and PolycubesBarequet, Gill / Shalah, Mira et al. | 2020
- 43
-
On the Collection of Fringe Subtrees in Random Binary TreesSeelbach Benkner, Louisa / Wagner, Stephan et al. | 2020
- 44
-
A Method to Prove the Nonrationality of Some Combinatorial Generating FunctionsBóna, Miklós et al. | 2020
- 45
-
Binary Decision Diagrams: From Tree Compaction to SamplingClément, Julien / Genitrini, Antoine et al. | 2020
- 46
-
Graph Sandwich Problem for the Property of Being Well-Covered and Partitionable into k Independent Sets and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} CliquesAlves, Sancrey Rodrigues / Couto, Fernanda / Faria, Luerbio / Gravier, Sylvain / Klein, Sulamita / Souza, Uéverton S. et al. | 2020
- 47
-
On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching NumberBlair, Jean R. S. / Heggernes, Pinar / Lima, Paloma T. / Lokshtanov, Daniel et al. | 2020
- 48
-
Steiner Trees for Hereditary Graph ClassesBodlaender, Hans L. / Brettell, Nick / Johnson, Matthew / Paesani, Giacomo / Paulusma, Daniël / van Leeuwen, Erik Jan et al. | 2020
- 49
-
On Some Subclasses of Split \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_1$$\end{document}-EPG GraphsDeniz, Zakir / Nivelle, Simon / Ries, Bernard / Schindl, David et al. | 2020
- 50
-
On the Helly Subclasses of Interval Bigraphs and Circular Arc BigraphsGroshaus, M. / Guedes, A. L. P. / Kolberg, F. S. et al. | 2020