A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners (Englisch)
Freier Zugriff
- Neue Suche nach: Bilò, Davide
- Weitere Informationen zu Bilò, Davide:
- https://orcid.org/0000-0003-3169-4300
- Neue Suche nach: Papadopoulos, Kleitos
- Weitere Informationen zu Papadopoulos, Kleitos:
- https://orcid.org/0000-0002-7086-0335
- Neue Suche nach: Bilò, Davide
- Weitere Informationen zu Bilò, Davide:
- https://orcid.org/0000-0003-3169-4300
- Neue Suche nach: Papadopoulos, Kleitos
- Weitere Informationen zu Papadopoulos, Kleitos:
- https://orcid.org/0000-0002-7086-0335
- Neue Suche nach: Hsu, Wen-Lian
- Neue Suche nach: Lee, Der-Tsai
- Neue Suche nach: Liao, Chung-Shou
In:
LIPIcs, Volume 123, ISAAC 2018
: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
;
123
;
7:1-7:12
;
2018
-
ISBN:
-
ISSN:
- Aufsatz (Konferenz) / Elektronische Ressource
-
Titel:A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
-
Beteiligte:Bilò, Davide ( Autor:in ) / Papadopoulos, Kleitos ( Autor:in ) / Hsu, Wen-Lian ( Herausgeber:in ) / Lee, Der-Tsai ( Herausgeber:in ) / Liao, Chung-Shou ( Herausgeber:in )
-
Erschienen in:LIPIcs, Volume 123, ISAAC 2018 : 29th International Symposium on Algorithms and Computation (ISAAC 2018) ; 123 ; 7:1-7:12Leibniz International Proceedings in Informatics (LIPIcs) ; 123 ; 7:1-7:12
-
Verlag:
- Neue Suche nach: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Erscheinungsdatum:06.12.2018
-
Format / Umfang:12 pages , 540796 byte
-
Anmerkungen:LIPIcs, Vol. 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018), pages 7:1-7:12
-
ISBN:
-
ISSN:
-
DOI:
-
Medientyp:Aufsatz (Konferenz)
-
Format:Elektronische Ressource
-
Sprache:Englisch
-
Schlagwörter:
-
Lizenzbestimmungen:
-
Datenquelle:
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 1
-
Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk)Teng, Shang-Hua et al. | 2018
- 2
-
Approximate Matchings in Massive Graphs via Local Structure (Invited Talk)Stein, Clifford et al. | 2018
- 3
-
Exploiting Sparsity for Bipartite HamiltonicityBjörklund, Andreas et al. | 2018
- 4
-
Opinion Forming in Erdös-Rényi Random Graph and ExpandersN. Zehmakan, Ahad et al. | 2018
- 5
-
Colouring (P_r+P_s)-Free GraphsKlimosová, Tereza / Malík, Josef / Masarík, Tomás / Novotná, Jana / Paulusma, Daniël / Slívová, Veronika et al. | 2018
- 6
-
The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph ClassesDucoffe, Guillaume / Popa, Alexandru et al. | 2018
- 7
-
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree SpannersBilò, Davide / Papadopoulos, Kleitos et al. | 2018
- 8
-
Efficient Enumeration of Dominating Sets for Sparse GraphsKurita, Kazuhiro / Wasa, Kunihiro / Arimura, Hiroki / Uno, Takeaki et al. | 2018
- 9
-
Complexity of Unordered CNF GamesRahman, Md Lutfar / Watson, Thomas et al. | 2018
- 10
-
Half-Duplex Communication ComplexityHoover, Kenneth / Impagliazzo, Russell / Mihajlin, Ivan / Smal, Alexander V. et al. | 2018
- 11
-
On the Complexity of Stable Fractional Hypergraph MatchingIshizuka, Takashi / Kamiyama, Naoyuki et al. | 2018
- 12
-
Deciding the Closure of Inconsistent Rooted Triples Is NP-CompleteJohnson, Matthew P. et al. | 2018
- 13
-
Computing Vertex-Disjoint Paths in Large Graphs Using MAOsPreißer, Johanna E. / Schmidt, Jens M. et al. | 2018
- 14
-
An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path NetworksBhattacharya, Binay / Higashikawa, Yuya / Kameda, Tsunehiko / Katoh, Naoki et al. | 2018
- 15
-
Computing Optimal Shortcuts for NetworksGarijo, Delia / Márquez, Alberto / Rodríguez, Natalia / Silveira, Rodrigo I. et al. | 2018
- 16
-
Algorithmic Channel DesignAvarikioti, Georgia / Wang, Yuyi / Wattenhofer, Roger et al. | 2018
- 17
-
Counting Connected Subgraphs with Maximum-Degree-Aware SievingBjörklund, Andreas / Husfeldt, Thore / Kaski, Petteri / Koivisto, Mikko et al. | 2018
- 18
-
Target Set Selection in Dense Graph ClassesDvorák, Pavel / Knop, Dusan / Toufar, Tomás et al. | 2018
- 19
-
Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC AlgorithmBjörklund, Andreas / Husfeldt, Thore et al. | 2018
- 20
-
Data-Compression for Parametrized Counting Problems on Sparse GraphsKim, Eun Jung / Serna, Maria / Thilikos, Dimitrios M. et al. | 2018
- 21
-
Planar Maximum Matching: Towards a Parallel AlgorithmDatta, Samir / Kulkarni, Raghav / Kumar, Ashish / Mukherjee, Anish et al. | 2018
- 22
-
Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free GraphsCzygrinow, Andrzej / Hanckowiak, Michal / Wawrzyniak, Wojciech / Witkowski, Marcin et al. | 2018
- 23
-
Proving the Turing Universality of Oritatami Co-Transcriptional FoldingGeary, Cody / Meunier, Pierre-Étienne / Schabanel, Nicolas / Seki, Shinnosuke et al. | 2018
- 24
-
Cluster Editing in Multi-Layer and Temporal GraphsChen, Jiehua / Molter, Hendrik / Sorge, Manuel / Suchý, Ondrej et al. | 2018
- 25
-
Parameterized Query Complexity of Hitting Set Using Stability of SunflowersBishnu, Arijit / Ghosh, Arijit / Kolay, Sudeshna / Mishra, Gopinath / Saurabh, Saket et al. | 2018
- 26
-
Approximate Minimum-Weight Matching with Outliers Under TranslationAgarwal, Pankaj K. / Kaplan, Haim / Kipper, Geva / Mulzer, Wolfgang / Rote, Günter / Sharir, Micha / Xiao, Allen et al. | 2018
- 27
-
New and Improved Algorithms for Unordered Tree InclusionAkutsu, Tatsuya / Jansson, Jesper / Li, Ruiming / Takasu, Atsuhiro / Tamura, Takeyuki et al. | 2018
- 28
-
Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite GraphsAngelini, Patrizio / Bekos, Michael A. / Kaufmann, Michael / Pfister, Maximilian / Ueckerdt, Torsten et al. | 2018
- 29
-
A Dichotomy Result for Cyclic-Order Traversing GamesChen, Yen-Ting / Tsai, Meng-Tsung / Tsai, Shi-Chun et al. | 2018
- 30
-
The b-Matching Problem in Distance-Hereditary Graphs and BeyondDucoffe, Guillaume / Popa, Alexandru et al. | 2018
- 31
-
New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds DecompositionFeng, Qilong / Tan, Guanlan / Zhu, Senmin / Fu, Bin / Wang, Jianxin et al. | 2018
- 32
-
Computing Approximate Statistical DiscrepancyMatheny, Michael / Phillips, Jeff M. et al. | 2018
- 33
-
Diversity Maximization in Doubling MetricsCevallos, Alfonso / Eisenbrand, Friedrich / Morell, Sarah et al. | 2018
- 34
-
On Polynomial Time Constructions of Minimum Height Decision TreeH. Bshouty, Nader / Makhoul, Waseem et al. | 2018
- 35
-
Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity NormAggarwal, Divesh / Mukhopadhyay, Priyanka et al. | 2018
- 36
-
An Adaptive Version of Brandes' Algorithm for Betweenness CentralityBentert, Matthias / Dittmann, Alexander / Kellerhals, Leon / Nichterlein, André / Niedermeier, Rolf et al. | 2018
- 37
-
Algorithms for Coloring Reconfiguration Under Recolorability ConstraintsOsawa, Hiroki / Suzuki, Akira / Ito, Takehiro / Zhou, Xiao et al. | 2018
- 38
-
A Cut Tree Representation for Pendant PairsLo, On-Hei S. / Schmidt, Jens M. et al. | 2018
- 39
-
Polyline Drawings with Topological ConstraintsDi Giacomo, Emilio / Eades, Peter / Liotta, Giuseppe / Meijer, Henk / Montecchiani, Fabrizio et al. | 2018
- 40
-
Almost Optimal Algorithms for Diameter-Optimally Augmenting TreesBilò, Davide et al. | 2018
- 41
-
Approximation Algorithms for Facial Cycles in Planar EmbeddingsDa Lozzo, Giordano / Rutter, Ignaz et al. | 2018
- 42
-
An Algorithm for the Maximum Weight Strongly Stable Matching ProblemKunysz, Adam et al. | 2018
- 43
-
Approximation Algorithm for Vertex Cover with Multiple Covering ConstraintsHong, Eunpyeong / Kao, Mong-Jen et al. | 2018
- 44
-
Correlation Clustering GeneralizedGleich, David F. / Veldt, Nate / Wirth, Anthony et al. | 2018
- 45
-
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based AlgorithmFicker, Annette M. C. / Erlebach, Thomas / Mihalák, Matús / Spieksma, Frits C. R. et al. | 2018
- 46
-
Coresets for Fuzzy K-Means with ApplicationsBlömer, Johannes / Brauer, Sascha / Bujna, Kathrin et al. | 2018
- 47
-
Streaming Algorithms for Planar Convex HullsFarach-Colton, Martín / Li, Meng / Tsai, Meng-Tsung et al. | 2018
- 48
-
Deterministic Treasure Hunt in the Plane with Angular HintsBouchard, Sébastien / Dieudonné, Yoann / Pelc, Andrzej / Petit, Franck et al. | 2018
- 49
-
Competitive Searching for a Line on a Line ArrangementBouts, Quirijn / Castermans, Thom / van Goethem, Arthur / van Kreveld, Marc / Meulemans, Wouter et al. | 2018
- 50
-
Stabbing Pairwise Intersecting Disks by Five PointsHar-Peled, Sariel / Kaplan, Haim / Mulzer, Wolfgang / Roditty, Liam / Seiferth, Paul / Sharir, Micha / Willert, Max et al. | 2018
- 51
-
Point Location in Incremental Planar SubdivisionsOh, Eunjin et al. | 2018
- 52
-
Convex Partial Transversals of Planar RegionsKeikha, Vahideh / van de Kerkhof, Mees / van Kreveld, Marc / Kostitsyna, Irina / Löffler, Maarten / Staals, Frank / Urhausen, Jérôme / Vermeulen, Jordi L. / Wiratma, Lionov et al. | 2018
- 53
-
Extending the Centerpoint Theorem to Multiple PointsPilz, Alexander / Schnider, Patrick et al. | 2018
- 54
-
Approximate Query Processing over Static Sets and Sliding WindowsBen Basat, Ran / Jo, Seungbum / Satti, Srinivasa Rao / Ugare, Shubham et al. | 2018
- 55
-
Multi-Finger Binary Search TreesChalermsook, Parinya / Goswami, Mayank / Kozma, László / Mehlhorn, Kurt / Saranurak, Thatchaphol et al. | 2018
- 56
-
On Counting Oracles for Path ProblemsBezáková, Ivona / Searns, Andrew et al. | 2018
- 57
-
Reconstructing Phylogenetic Tree From Multipartite Quartet SystemHirai, Hiroshi / Iwamasa, Yuni et al. | 2018
- 58
-
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal DomainArseneva, Elena / Chiu, Man-Kwun / Korman, Matias / Markovic, Aleksandar / Okamoto, Yoshio / Ooms, Aurélien / van Renssen, André / Roeloffzen, Marcel et al. | 2018
- 59
-
Minimizing Distance-to-Sight in Polygonal DomainsOh, Eunjin et al. | 2018
- 60
-
Partially Walking a PolygonAurenhammer, Franz / Steinkogler, Michael / Klein, Rolf et al. | 2018
- 61
-
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell ComplexityChan, Timothy M. / van Dijk, Thomas C. / Fleszar, Krzysztof / Spoerhase, Joachim / Wolff, Alexander et al. | 2018
- 62
-
Impatient Online MatchingLiu, Xingwu / Pan, Zhida / Wang, Yuyi / Wattenhofer, Roger et al. | 2018
- 63
-
Extensions of Self-Improving SortersCheng, Siu-Wing / Yan, Lie et al. | 2018
- 64
-
Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance BookingsLuo, Kelin / Erlebach, Thomas / Xu, Yinfeng et al. | 2018
- 65
-
Packing Returning SecretariesHoefer, Martin / Wilhelmi, Lisa et al. | 2018
- 66
-
Simple 2^f-Color Choice DictionariesKammer, Frank / Sajenko, Andrej et al. | 2018
- 67
-
Succinct Data Structures for Chordal GraphsMunro, J. Ian / Wu, Kaiyu et al. | 2018
- 68
-
Tree Path Majority Data StructuresGagie, Travis / He, Meng / Navarro, Gonzalo et al. | 2018
- 69
-
Encoding Two-Dimensional Range Top-k Queries RevisitedJo, Seungbum / Satti, Srinivasa Rao et al. | 2018
- 70
-
Longest Unbordered Factor in Quasilinear TimeKociumaka, Tomasz / Kundu, Ritu / Mohamed, Manal / Pissis, Solon P. et al. | 2018
- 71
-
Packing Sporadic Real-Time Tasks on Identical Multiprocessor SystemsChen, Jian-Jia / Bansal, Nikhil / Chakraborty, Samarjit / von der Brüggen, Georg et al. | 2018
- 72
-
A Relaxed FPTAS for Chance-Constrained KnapsackShabtai, Galia / Raz, Danny / Shavitt, Yuval et al. | 2018
- 73
-
Covering Clients with Types and BudgetsFotakis, Dimitris / Gourvès, Laurent / Mathieu, Claire / Srivastav, Abhinav et al. | 2018