Improved Approximation Algorithms for Box Contact Representations (English)
- New search for: Bekos, Michael A.
- New search for: Dijk, Thomas C.
- New search for: Fink, Martin
- New search for: Kindermann, Philipp
- New search for: Kobourov, Stephen
- New search for: Pupyrev, Sergey
- New search for: Spoerhase, Joachim
- New search for: Wolff, Alexander
- New search for: Bekos, Michael A.
- New search for: Dijk, Thomas C.
- New search for: Fink, Martin
- New search for: Kindermann, Philipp
- New search for: Kobourov, Stephen
- New search for: Pupyrev, Sergey
- New search for: Spoerhase, Joachim
- New search for: Wolff, Alexander
In:
Algorithms - ESA 2014
;
87-99
;
2014
- Article/Chapter (Book) / Electronic Resource
-
Title:Improved Approximation Algorithms for Box Contact Representations
-
Contributors:Bekos, Michael A. ( author ) / Dijk, Thomas C. ( author ) / Fink, Martin ( author ) / Kindermann, Philipp ( author ) / Kobourov, Stephen ( author ) / Pupyrev, Sergey ( author ) / Spoerhase, Joachim ( author ) / Wolff, Alexander ( author )
-
Published in:Algorithms - ESA 2014 ; 87-99Lecture Notes in Computer Science ; 8737 ; 87-99
-
Publisher:
- New search for: Springer Berlin Heidelberg
-
Place of publication:Berlin, Heidelberg
-
Publication date:2014-01-01
-
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
-
Losing Weight by Gaining EdgesAbboud, Amir / Lewi, Kevin / Williams, Ryan et al. | 2014
- 13
-
Optimal Coordination Mechanisms for Multi-job Scheduling GamesAbed, Fidaa / Correa, José R. / Huang, Chien-Chung et al. | 2014
- 25
-
Theory and Practice of Chunked SequencesAcar, Umut A. / Charguéraud, Arthur / Rainey, Mike et al. | 2014
- 37
-
Convex Hulls under UncertaintyAgarwal, Pankaj K. / Har-Peled, Sariel / Suri, Subhash / Yıldız, Hakan / Zhang, Wuzhou et al. | 2014
- 49
-
The Space-Stretch-Time Tradeoff in Distance OraclesAgarwal, Rachit et al. | 2014
- 61
-
Distribution-Sensitive Construction of the Greedy SpannerAlewijnse, Sander P. A. / Bouts, Quirijn W. / Brink, Alex P. et al. | 2014
- 74
-
Recognizing Shrinkable Complexes Is NP-CompleteAttali, Dominique / Devillers, Olivier / Glisse, Marc / Lazard, Sylvain et al. | 2014
- 87
-
Improved Approximation Algorithms for Box Contact RepresentationsBekos, Michael A. / Dijk, Thomas C. / Fink, Martin / Kindermann, Philipp / Kobourov, Stephen / Pupyrev, Sergey / Spoerhase, Joachim / Wolff, Alexander et al. | 2014
- 100
-
Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and AlgorithmsBen-Avraham, Rinat / Henze, Matthias / Jaume, Rafel / Keszegh, Balázs / Raz, Orit E. / Sharir, Micha / Tubis, Igor et al. | 2014
- 112
-
The Batched Predecessor Problem in External MemoryBender, Michael A. / Farach-Colton, Martín / Goswami, Mayank / Medjedovic, Dzejla / Montes, Pablo / Tsai, Meng-Tsung et al. | 2014
- 125
-
Polynomial Decompositions in Polynomial TimeBhattacharyya, Arnab et al. | 2014
- 137
-
Fault-Tolerant Approximate Shortest-Path TreesBilò, Davide / Gualà, Luciano / Leucci, Stefano / Proietti, Guido et al. | 2014
- 149
-
Fast Witness Extraction Using a Decision OracleBjörklund, Andreas / Kaski, Petteri / Kowalik, Łukasz et al. | 2014
- 161
-
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky ModelBläsius, Thomas / Brückner, Guido / Rutter, Ignaz et al. | 2014
- 173
-
A Subexponential Parameterized Algorithm for Proper Interval CompletionBliznets, Ivan / Fomin, Fedor V. / Pilipczuk, Marcin / Pilipczuk, Michał et al. | 2014
- 185
-
Computing Persistent Homology with Various Coefficient Fields in a Single PassBoissonnat, Jean-Daniel / Maria, Clément et al. | 2014
- 197
-
De-anonymization of Heterogeneous Random Graphs in Quasilinear TimeBringmann, Karl / Friedrich, Tobias / Krohmer, Anton et al. | 2014
- 209
-
Competitive Algorithms for Restricted Caching and Matroid CachingBuchbinder, Niv / Chen, Shahar / Naor, Joseph (Seffi) et al. | 2014
- 222
-
Improved Algorithms for Resource Allocation under Varying CapacityChakaravarthy, Venkatesan T. / Choudhury, Anamitra R. / Gupta, Shalmoli / Roy, Sambuddha / Sabharwal, Yogish et al. | 2014
- 235
-
Nearly Tight Approximability Results for Minimum Biclique Cover and PartitionChalermsook, Parinya / Heydrich, Sandy / Holm, Eugenia / Karrenbauer, Andreas et al. | 2014
- 247
-
Succinct Indices for Path Minimum, with Applications to Path ReportingChan, Timothy M. / He, Meng / Munro, J. Ian / Zhou, Gelin et al. | 2014
- 260
-
Online Bipartite Matching with Decomposable WeightsCharikar, Moses / Henzinger, Monika / Nguyễn, Huy L. et al. | 2014
- 272
-
A Faster Algorithm for Computing Straight SkeletonsCheng, Siu-Wing / Mencel, Liam / Vigneron, Antoine et al. | 2014
- 284
-
Optimal Time-Space Tradeoff for the 2D Convex-Hull ProblemDarwish, Omar / Elmasry, Amr et al. | 2014
- 296
-
Cache-Oblivious PersistenceDavoodi, Pooya / Fineman, Jeremy T. / Iacono, John / Özkan, Özgür et al. | 2014
- 309
-
Lightweight Approximate SelectionDean, Brian C. / Jalasutram, Rommel / Waters, Chad et al. | 2014
- 321
-
Robust Distance Queries on Massive NetworksDelling, Daniel / Goldberg, Andrew V. / Pajor, Thomas / Werneck, Renato F. et al. | 2014
- 334
-
A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-DepthDvořák, Zdeněk / Kupec, Martin / Tůma, Vojtěch et al. | 2014
- 346
-
Large Independent Sets in Triangle-Free Planar GraphsDvořák, Zdeněk / Mnich, Matthias et al. | 2014
- 358
-
GRASP. Extending Graph Separators for the Single-Source Shortest-Path ProblemEfentakis, Alexandros / Pfoser, Dieter et al. | 2014
- 371
-
Switching Colouring of G(n,d/n) for Sampling up to Gibbs Uniqueness ThresholdEfthymiou, Charilaos et al. | 2014
- 382
-
From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?Ene, Alina / Nguyễn, Huy L. et al. | 2014
- 394
-
Deterministic Stateless Centralized Local Algorithms for Bounded Degree GraphsEven, Guy / Medina, Moti / Ron, Dana et al. | 2014
- 406
-
Bicriteria Data Compression: Efficient and UsableFarruggia, Andrea / Ferragina, Paolo / Venturini, Rossano et al. | 2014
- 418
-
Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected GraphsFerreira, Rui / Grossi, Roberto / Rizzi, Romeo / Sacomoto, Gustavo / Sagot, Marie-France et al. | 2014
- 430
-
LP Approaches to Improved Approximation for Clique Transversal in Perfect GraphsFiorini, Samuel / Krithika, R. / Narayanaswamy, N. S. / Raman, Venkatesh et al. | 2014
- 443
-
Representative Sets of Product FamiliesFomin, Fedor V. / Lokshtanov, Daniel / Panolan, Fahad / Saurabh, Saket et al. | 2014
- 455
-
Weighted Ancestors in Suffix TreesGawrychowski, Paweł / Lewenstein, Moshe / Nicholson, Patrick K. et al. | 2014
- 467
-
Improved Practical Matrix Sketching with GuaranteesGhashami, Mina / Desai, Amey / Phillips, Jeff M. et al. | 2014
- 480
-
Computing Regions Decomposable into m StarsGibson, Matt / Varadarajan, Kasturi / Wu, Xiaodong et al. | 2014
- 492
-
The Parameterized Complexity of Graph CyclabilityGolovach, Petr A. / Kamiński, Marcin / Maniatis, Spyridon / Thilikos, Dimitrios M. et al. | 2014
- 505
-
Dimension Reduction via Colour RefinementGrohe, Martin / Kersting, Kristian / Mladenov, Martin / Selman, Erkal et al. | 2014
- 517
-
How Experts Can Solve LPs OnlineGupta, Anupam / Molinaro, Marco et al. | 2014
- 530
-
Parameterized Complexity of the k-Arc Chinese Postman ProblemGutin, Gregory / Jones, Mark / Sheng, Bin et al. | 2014
- 542
-
Approximating the Maximum Overlap of Polygons under TranslationHar-Peled, Sariel / Roy, Subhro et al. | 2014
- 554
-
Ordering without Forbidden PatternsHell, Pavol / Mohar, Bojan / Rafiey, Arash et al. | 2014
- 566
-
Halving Balls in Deterministic Linear TimeHoffmann, Michael / Kusters, Vincent / Miltzow, Tillmann et al. | 2014
- 579
-
Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph ClassesJansen, Bart M. P. et al. | 2014
- 592
-
Optimal Parallel Quantum Query AlgorithmsJeffery, Stacey / Magniez, Frederic / Wolf, Ronald et al. | 2014
- 605
-
Sublinear Space Algorithms for the Longest Common Substring ProblemKociumaka, Tomasz / Starikovskaya, Tatiana / Vildhøj, Hjalte Wedel et al. | 2014
- 618
-
Nested Set UnionLarkin, Daniel H. / Tarjan, Robert E. et al. | 2014
- 630
-
Improved Explicit Data Structures in the Bitprobe ModelLewenstein, Moshe / Munro, J. Ian / Nicholson, Patrick K. / Raman, Venkatesh et al. | 2014
- 642
-
Deeper Local Search for Better Approximation on Maximum Internal Spanning TreesLi, Wenjun / Chen, Jianer / Wang, Jianxin et al. | 2014
- 654
-
FPTAS for Counting Weighted Edge CoversLiu, Jingcheng / Lu, Pinyan / Zhang, Chihao et al. | 2014
- 666
-
Solving Multicut Faster Than 2 nLokshtanov, Daniel / Saurabh, Saket / Suchý, Ondřej et al. | 2014
- 677
-
Tight Bounds for Active Self-assembly Using an Insertion PrimitiveMalchik, Caleb / Winslow, Andrew et al. | 2014
- 689
-
Trace Reconstruction RevisitedMcGregor, Andrew / Price, Eric / Vorotnikova, Sofya et al. | 2014
- 701
-
PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction HierarchiesMerz, Florian / Sanders, Peter et al. | 2014
- 713
-
Polynomial-Time Approximation Schemes for Circle Packing ProblemsMiyazawa, Flávio K. / Pedrosa, Lehilton L. C. / Schouery, Rafael C. S. / Sviridenko, Maxim / Wakabayashi, Yoshiko et al. | 2014
- 725
-
Document Retrieval on Repetitive CollectionsNavarro, Gonzalo / Puglisi, Simon J. / Sirén, Jouni et al. | 2014
- 737
-
An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic GraphsNewman, Alantha et al. | 2014
- 750
-
The Input/Output Complexity of Sparse Matrix MultiplicationPagh, Rasmus / Stöckel, Morten et al. | 2014
- 762
-
Faster FPTASes for Counting and Random Generation of Knapsack SolutionsRizzi, Romeo / Tomescu, Alexandru I. et al. | 2014
- 774
-
Improved Guarantees for Tree Cut SparsifiersRäcke, Harald / Shah, Chintan et al. | 2014
- 786
-
Representative Families: A Unified Tradeoff-Based ApproachShachnai, Hadas / Zehavi, Meirav et al. | 2014
- 798
-
A Branch and Price Procedure for the Container Premarshalling ProblemBrink, Martijn / Zwaan, Ruben et al. | 2014
- 810
-
Space-Efficient Randomized Algorithms for K-SUMWang, Joshua R. et al. | 2014
- 830
-
Equivalence between Priority Queues and Sorting in External MemoryWei, Zhewei / Yi, Ke et al. | 2014
- 842
-
Amortized Bounds for Dynamic Orthogonal Range ReportingWilkinson, Bryan T. et al. | 2014