SWAT 2022 June 27-29, 2022, Tórshavn, Faroe Islands

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)



Artur Czumaj and Qin Xin (Eds.)
ISBN 978-3-95977-236-5, LIPICS Vol. 227 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 11 MB)
Search Publication Server

Authors
  • A. Akitaya, Hugo
  • Adjiashvili, David
  • Agarwal, Pankaj K.
  • Ameer, Safwa
  • Angelini, Patrizio
  • Antoniadis, Antonios
  • Aronov, Boris
  • Bannach, Max
  • Bar-Noy, Amotz
  • Bazgan, Cristina
  • Bekos, Michael A.
  • Berendsohn, Benjamin Aram
  • Bergold, Helena
  • Bertschinger, Daniel
  • Bille, Philip
  • Böhnlein, Toni
  • Bose, Prosenjit
  • Boyar, Joan
  • Casel, Katrin
  • Cazals, Pierre
  • Chakraborty, Sankardeep
  • Cleve, Jonas
  • Czumaj, Artur
  • Da Lozzo, Giordano
  • de Berg, Mark
  • Demaine, Erik D.
  • Dvořák, Zdeněk
  • Elkin, Michael
  • Favrholdt, Lene M.
  • Fioravantes, Foivos
  • Fleischmann, Pamela
  • Fluschnik, Till
  • Gan, Junhao
  • Gąsieniec, Leszek
  • Gibson-Lopez, Matt
  • Gitlitz, Yuval
  • Gørtz, Inge Li
  • Grelier, Nicolas
  • Gronemann, Martin
  • Hommelsheim, Felix
  • Huang, Chien-Chung
  • Inamdar, Tanmay
  • Jabbarzade, Peyman
  • Katz, Matthew J.
  • Kisfaludi-Bak, Sándor
  • Knorr, Kristin
  • Korman, Matias
  • Kostitsyna, Irina
  • Krohn, Erik
  • Kunz, Pascal
  • Laekhanukit, Bundit
  • Larsen, Kim S.
  • Löffler, Maarten
  • Mann, Enrico
  • Melissinos, Nikolaos
  • Montecchiani, Fabrizio
  • Morin, Pat
  • M. Reddy, Meghana
  • Mühlenthaler, Moritz
  • Mulzer, Wolfgang
  • Neiman, Ofer
  • Niedermeier, Rolf
  • Odak, Saeed
  • Parada, Irene
  • Peleg, David
  • Perz, Daniel
  • Raghvendra, Sharath
  • Rahman, Md Lutfar
  • Rawitz, Dror
  • Renken, Malte
  • Sadakane, Kunihiko
  • Sadhukhan, Arpan
  • Satti, Srinivasa Rao
  • Schaudt, Oliver
  • Schnider, Patrick
  • Sellier, François
  • Shahkarami, Golnoosh
  • Shirzadian, Pouyan
  • Skambath, Malte
  • Sonke, Willem
  • Sowle, Rachita
  • Speckmann, Bettina
  • Spieksma, Frits
  • Stachowiak, Grzegorz
  • Stordalen, Tord
  • Tappini, Alessandra
  • Thorup, Mikkel
  • Triommatis, Theofilos
  • Uehara, Ryuhei
  • Varadarajan, Kasturi
  • Vaz, Daniel
  • Wang, Haitao
  • Wang, Qing
  • Watson, Thomas
  • Wirth, Anthony
  • Wulms, Jules
  • Xin, Qin
  • Yanagita, Tatsuya
  • Zamarripa, Serge
  • Zhang, Xin
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Czumaj, Artur ; Xin, Qin

    Abstract | Document (483 KB) | BibTeX

    On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper)
    Authors: Bar-Noy, Amotz ; Böhnlein, Toni ; Peleg, David ; Rawitz, Dror

    Abstract | Document (940 KB) | BibTeX

    Time, Clocks and Efficiency of Population Protocols (Invited Paper)
    Authors: Gąsieniec, Leszek ; Stachowiak, Grzegorz

    Abstract | Document (422 KB) | BibTeX

    Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper)
    Authors: Thorup, Mikkel

    Abstract | Document (412 KB) | BibTeX

    Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
    Authors: A. Akitaya, Hugo ; Demaine, Erik D. ; Korman, Matias ; Kostitsyna, Irina ; Parada, Irene ; Sonke, Willem ; Speckmann, Bettina ; Uehara, Ryuhei ; Wulms, Jules

    Abstract | Document (1,615 KB) | BibTeX

    Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults
    Authors: Adjiashvili, David ; Hommelsheim, Felix ; Mühlenthaler, Moritz ; Schaudt, Oliver

    Abstract | Document (809 KB) | BibTeX

    An Improved ε-Approximation Algorithm for Geometric Bipartite Matching
    Authors: Agarwal, Pankaj K. ; Raghvendra, Sharath ; Shirzadian, Pouyan ; Sowle, Rachita

    Abstract | Document (977 KB) | BibTeX

    On the Visibility Graphs of Pseudo-Polygons: Recognition and Reconstruction
    Authors: Ameer, Safwa ; Gibson-Lopez, Matt ; Krohn, Erik ; Wang, Qing

    Abstract | Document (726 KB) | BibTeX

    Recognizing Map Graphs of Bounded Treewidth
    Authors: Angelini, Patrizio ; Bekos, Michael A. ; Da Lozzo, Giordano ; Gronemann, Martin ; Montecchiani, Fabrizio ; Tappini, Alessandra

    Abstract | Document (1,136 KB) | BibTeX

    A Novel Prediction Setup for Online Speed-Scaling
    Authors: Antoniadis, Antonios ; Jabbarzade, Peyman ; Shahkarami, Golnoosh

    Abstract | Document (781 KB) | BibTeX

    On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
    Authors: Antoniadis, Antonios ; Kisfaludi-Bak, Sándor ; Laekhanukit, Bundit ; Vaz, Daniel

    Abstract | Document (911 KB) | BibTeX

    Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors
    Authors: Aronov, Boris ; Katz, Matthew J.

    Abstract | Document (784 KB) | BibTeX

    MaxSAT with Absolute Value Functions: A Parameterized Perspective
    Authors: Bannach, Max ; Fleischmann, Pamela ; Skambath, Malte

    Abstract | Document (821 KB) | BibTeX

    Dense Graph Partitioning on Sparse and Dense Graphs
    Authors: Bazgan, Cristina ; Casel, Katrin ; Cazals, Pierre

    Abstract | Document (814 KB) | BibTeX

    The Diameter of Caterpillar Associahedra
    Authors: Berendsohn, Benjamin Aram

    Abstract | Document (713 KB) | BibTeX

    Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
    Authors: de Berg, Mark ; Sadhukhan, Arpan ; Spieksma, Frits

    Abstract | Document (1,001 KB) | BibTeX

    Well-Separation and Hyperplane Transversals in High Dimensions
    Authors: Bergold, Helena ; Bertschinger, Daniel ; Grelier, Nicolas ; Mulzer, Wolfgang ; Schnider, Patrick

    Abstract | Document (747 KB) | BibTeX

    Lions and Contamination: Monotone Clearings
    Authors: Bertschinger, Daniel ; M. Reddy, Meghana ; Mann, Enrico

    Abstract | Document (697 KB) | BibTeX

    Predecessor on the Ultra-Wide Word RAM
    Authors: Bille, Philip ; Gørtz, Inge Li ; Stordalen, Tord

    Abstract | Document (771 KB) | BibTeX

    An Optimal Algorithm for Product Structure in Planar Graphs
    Authors: Bose, Prosenjit ; Morin, Pat ; Odak, Saeed

    Abstract | Document (760 KB) | BibTeX

    Online Unit Profit Knapsack with Untrusted Predictions
    Authors: Boyar, Joan ; Favrholdt, Lene M. ; Larsen, Kim S.

    Abstract | Document (800 KB) | BibTeX

    Nearest-Neighbor Decompositions of Drawings
    Authors: Cleve, Jonas ; Grelier, Nicolas ; Knorr, Kristin ; Löffler, Maarten ; Mulzer, Wolfgang ; Perz, Daniel

    Abstract | Document (1,289 KB) | BibTeX

    Approximation Metatheorems for Classes with Bounded Expansion
    Authors: Dvořák, Zdeněk

    Abstract | Document (773 KB) | BibTeX

    Almost Shortest Paths with Near-Additive Error in Weighted Graphs
    Authors: Elkin, Michael ; Gitlitz, Yuval ; Neiman, Ofer

    Abstract | Document (760 KB) | BibTeX

    Complexity of Finding Maximum Locally Irregular Induced Subgraphs
    Authors: Fioravantes, Foivos ; Melissinos, Nikolaos ; Triommatis, Theofilos

    Abstract | Document (834 KB) | BibTeX

    An Almost Optimal Algorithm for Unbounded Search with Noisy Information
    Authors: Gan, Junhao ; Wirth, Anthony ; Zhang, Xin

    Abstract | Document (894 KB) | BibTeX

    Optimal Bounds for Weak Consistent Digital Rays in 2D
    Authors: Gibson-Lopez, Matt ; Zamarripa, Serge

    Abstract | Document (960 KB) | BibTeX

    Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms
    Authors: Huang, Chien-Chung ; Sellier, François

    Abstract | Document (711 KB) | BibTeX

    Non-Uniform k-Center and Greedy Clustering
    Authors: Inamdar, Tanmay ; Varadarajan, Kasturi

    Abstract | Document (904 KB) | BibTeX

    Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives
    Authors: Kunz, Pascal ; Fluschnik, Till ; Niedermeier, Rolf ; Renken, Malte

    Abstract | Document (1,482 KB) | BibTeX

    A Scalable Work Function Algorithm for the k-Server Problem
    Authors: Raghvendra, Sharath ; Sowle, Rachita

    Abstract | Document (903 KB) | BibTeX

    Erdős-Selfridge Theorem for Nonmonotone CNFs
    Authors: Rahman, Md Lutfar ; Watson, Thomas

    Abstract | Document (603 KB) | BibTeX

    Unit-Disk Range Searching and Applications
    Authors: Wang, Haitao

    Abstract | Document (799 KB) | BibTeX

    Space-Efficient Data Structure for Posets with Applications
    Authors: Yanagita, Tatsuya ; Chakraborty, Sankardeep ; Sadakane, Kunihiko ; Satti, Srinivasa Rao

    Abstract | Document (776 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI