for Journals by Title or ISSN
for Articles by Keywords

Publisher: Springer-Verlag (Total: 2350 journals)

 A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

        1 2 3 4 5 6 7 8 | Last   [Sort by number of followers]   [Restore default list]

Showing 1 - 200 of 2350 Journals sorted alphabetically
3D Printing in Medicine     Open Access   (Followers: 1)
3D Research     Hybrid Journal   (Followers: 21, SJR: 0.222, CiteScore: 1)
4OR: A Quarterly J. of Operations Research     Hybrid Journal   (Followers: 10, SJR: 0.825, CiteScore: 1)
AAPS J.     Hybrid Journal   (Followers: 22, SJR: 1.118, CiteScore: 4)
AAPS PharmSciTech     Hybrid Journal   (Followers: 7, SJR: 0.752, CiteScore: 3)
Abdominal Imaging     Hybrid Journal   (Followers: 15, SJR: 0.866, CiteScore: 2)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 4, SJR: 0.439, CiteScore: 0)
Academic Psychiatry     Full-text available via subscription   (Followers: 25, SJR: 0.53, CiteScore: 1)
Academic Questions     Hybrid Journal   (Followers: 8, SJR: 0.106, CiteScore: 0)
Accreditation and Quality Assurance: J. for Quality, Comparability and Reliability in Chemical Measurement     Hybrid Journal   (Followers: 27, SJR: 0.316, CiteScore: 1)
Acoustical Physics     Hybrid Journal   (Followers: 11, SJR: 0.359, CiteScore: 1)
Acoustics Australia     Hybrid Journal   (SJR: 0.232, CiteScore: 1)
Acta Analytica     Hybrid Journal   (Followers: 7, SJR: 0.367, CiteScore: 0)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1, SJR: 0.675, CiteScore: 1)
Acta Biotheoretica     Hybrid Journal   (Followers: 4, SJR: 0.284, CiteScore: 1)
Acta Diabetologica     Hybrid Journal   (Followers: 18, SJR: 1.587, CiteScore: 3)
Acta Endoscopica     Hybrid Journal   (Followers: 1)
acta ethologica     Hybrid Journal   (Followers: 4, SJR: 0.769, CiteScore: 1)
Acta Geochimica     Hybrid Journal   (Followers: 7, SJR: 0.24, CiteScore: 1)
Acta Geodaetica et Geophysica     Hybrid Journal   (Followers: 2, SJR: 0.305, CiteScore: 1)
Acta Geophysica     Hybrid Journal   (Followers: 10, SJR: 0.312, CiteScore: 1)
Acta Geotechnica     Hybrid Journal   (Followers: 7, SJR: 1.588, CiteScore: 3)
Acta Informatica     Hybrid Journal   (Followers: 5, SJR: 0.517, CiteScore: 1)
Acta Mathematica     Hybrid Journal   (Followers: 12, SJR: 7.066, CiteScore: 3)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2, SJR: 0.452, CiteScore: 1)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 6, SJR: 0.379, CiteScore: 1)
Acta Mathematica Vietnamica     Hybrid Journal   (SJR: 0.27, CiteScore: 0)
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal   (SJR: 0.208, CiteScore: 0)
Acta Mechanica     Hybrid Journal   (Followers: 21, SJR: 1.04, CiteScore: 2)
Acta Mechanica Sinica     Hybrid Journal   (Followers: 5, SJR: 0.607, CiteScore: 2)
Acta Metallurgica Sinica (English Letters)     Hybrid Journal   (Followers: 7, SJR: 0.576, CiteScore: 2)
Acta Meteorologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.638, CiteScore: 1)
Acta Neurochirurgica     Hybrid Journal   (Followers: 6, SJR: 0.822, CiteScore: 2)
Acta Neurologica Belgica     Hybrid Journal   (Followers: 1, SJR: 0.376, CiteScore: 1)
Acta Neuropathologica     Hybrid Journal   (Followers: 5, SJR: 7.589, CiteScore: 12)
Acta Oceanologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.334, CiteScore: 1)
Acta Physiologiae Plantarum     Hybrid Journal   (Followers: 2, SJR: 0.574, CiteScore: 2)
Acta Politica     Hybrid Journal   (Followers: 15, SJR: 0.605, CiteScore: 1)
Activitas Nervosa Superior     Hybrid Journal   (SJR: 0.147, CiteScore: 0)
adhäsion KLEBEN & DICHTEN     Hybrid Journal   (Followers: 8, SJR: 0.103, CiteScore: 0)
ADHD Attention Deficit and Hyperactivity Disorders     Hybrid Journal   (Followers: 23, SJR: 0.72, CiteScore: 2)
Adhesion Adhesives & Sealants     Hybrid Journal   (Followers: 9)
Administration and Policy in Mental Health and Mental Health Services Research     Partially Free   (Followers: 16, SJR: 1.005, CiteScore: 2)
Adsorption     Hybrid Journal   (Followers: 4, SJR: 0.703, CiteScore: 2)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 4, SJR: 0.698, CiteScore: 1)
Advances in Atmospheric Sciences     Hybrid Journal   (Followers: 37, SJR: 0.956, CiteScore: 2)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 19, SJR: 0.812, CiteScore: 1)
Advances in Contraception     Hybrid Journal   (Followers: 3)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 54, SJR: 1.09, CiteScore: 1)
Advances in Gerontology     Partially Free   (Followers: 8, SJR: 0.144, CiteScore: 0)
Advances in Health Sciences Education     Hybrid Journal   (Followers: 28, SJR: 1.64, CiteScore: 2)
Advances in Manufacturing     Hybrid Journal   (Followers: 3, SJR: 0.475, CiteScore: 2)
Advances in Polymer Science     Hybrid Journal   (Followers: 44, SJR: 1.04, CiteScore: 3)
Advances in Therapy     Hybrid Journal   (Followers: 5, SJR: 1.075, CiteScore: 3)
Aegean Review of the Law of the Sea and Maritime Law     Hybrid Journal   (Followers: 6)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2, SJR: 0.517, CiteScore: 1)
Aerobiologia     Hybrid Journal   (Followers: 3, SJR: 0.673, CiteScore: 2)
Aesthetic Plastic Surgery     Hybrid Journal   (Followers: 9, SJR: 0.825, CiteScore: 1)
African Archaeological Review     Hybrid Journal   (Followers: 16, SJR: 0.862, CiteScore: 1)
Afrika Matematika     Hybrid Journal   (Followers: 1, SJR: 0.235, CiteScore: 0)
AGE     Hybrid Journal   (Followers: 7)
Ageing Intl.     Hybrid Journal   (Followers: 7, SJR: 0.39, CiteScore: 1)
Aggiornamenti CIO     Hybrid Journal   (Followers: 1)
Aging Clinical and Experimental Research     Hybrid Journal   (Followers: 3, SJR: 0.67, CiteScore: 2)
Agricultural Research     Hybrid Journal   (Followers: 6, SJR: 0.276, CiteScore: 1)
Agriculture and Human Values     Hybrid Journal   (Followers: 14, SJR: 1.173, CiteScore: 3)
Agroforestry Systems     Hybrid Journal   (Followers: 20, SJR: 0.663, CiteScore: 1)
Agronomy for Sustainable Development     Hybrid Journal   (Followers: 12, SJR: 1.864, CiteScore: 6)
AI & Society     Hybrid Journal   (Followers: 8, SJR: 0.227, CiteScore: 1)
AIDS and Behavior     Hybrid Journal   (Followers: 14, SJR: 1.792, CiteScore: 3)
Air Quality, Atmosphere & Health     Hybrid Journal   (Followers: 4, SJR: 0.862, CiteScore: 3)
Akupunktur & Aurikulomedizin     Full-text available via subscription   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 6, SJR: 0.531, CiteScore: 0)
Algebra Universalis     Hybrid Journal   (Followers: 2, SJR: 0.583, CiteScore: 1)
Algebras and Representation Theory     Hybrid Journal   (Followers: 1, SJR: 1.095, CiteScore: 1)
Algorithmica     Hybrid Journal   (Followers: 9, SJR: 0.56, CiteScore: 1)
Allergo J.     Full-text available via subscription   (Followers: 1, SJR: 0.234, CiteScore: 0)
Allergo J. Intl.     Hybrid Journal   (Followers: 2)
Alpine Botany     Hybrid Journal   (Followers: 5, SJR: 1.11, CiteScore: 3)
ALTEX : Alternatives to Animal Experimentation     Open Access   (Followers: 3)
AMBIO     Hybrid Journal   (Followers: 10, SJR: 1.569, CiteScore: 4)
American J. of Cardiovascular Drugs     Hybrid Journal   (Followers: 16, SJR: 0.951, CiteScore: 3)
American J. of Community Psychology     Hybrid Journal   (Followers: 29, SJR: 1.329, CiteScore: 2)
American J. of Criminal Justice     Hybrid Journal   (Followers: 8, SJR: 0.772, CiteScore: 1)
American J. of Cultural Sociology     Hybrid Journal   (Followers: 16, SJR: 0.46, CiteScore: 1)
American J. of Dance Therapy     Hybrid Journal   (Followers: 4, SJR: 0.181, CiteScore: 0)
American J. of Potato Research     Hybrid Journal   (Followers: 2, SJR: 0.611, CiteScore: 1)
American J. of Psychoanalysis     Hybrid Journal   (Followers: 21, SJR: 0.314, CiteScore: 0)
American Sociologist     Hybrid Journal   (Followers: 12, SJR: 0.35, CiteScore: 0)
Amino Acids     Hybrid Journal   (Followers: 8, SJR: 1.135, CiteScore: 3)
AMS Review     Partially Free   (Followers: 4)
Analog Integrated Circuits and Signal Processing     Hybrid Journal   (Followers: 7, SJR: 0.211, CiteScore: 1)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 5, SJR: 0.536, CiteScore: 1)
Analysis in Theory and Applications     Hybrid Journal   (Followers: 1)
Analysis of Verbal Behavior     Hybrid Journal   (Followers: 5)
Analytical and Bioanalytical Chemistry     Hybrid Journal   (Followers: 32, SJR: 0.978, CiteScore: 3)
Anatomical Science Intl.     Hybrid Journal   (Followers: 2, SJR: 0.367, CiteScore: 1)
Angewandte Schmerztherapie und Palliativmedizin     Hybrid Journal  
Angiogenesis     Hybrid Journal   (Followers: 3, SJR: 2.177, CiteScore: 5)
Animal Cognition     Hybrid Journal   (Followers: 19, SJR: 1.389, CiteScore: 3)
Annales françaises de médecine d'urgence     Hybrid Journal   (Followers: 1, SJR: 0.192, CiteScore: 0)
Annales Henri Poincaré     Hybrid Journal   (Followers: 3, SJR: 1.097, CiteScore: 2)
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4, SJR: 0.438, CiteScore: 0)
Annali dell'Universita di Ferrara     Hybrid Journal   (SJR: 0.429, CiteScore: 0)
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1, SJR: 1.197, CiteScore: 1)
Annals of Biomedical Engineering     Hybrid Journal   (Followers: 18, SJR: 1.042, CiteScore: 3)
Annals of Combinatorics     Hybrid Journal   (Followers: 4, SJR: 0.932, CiteScore: 1)
Annals of Data Science     Hybrid Journal   (Followers: 12)
Annals of Dyslexia     Hybrid Journal   (Followers: 10, SJR: 0.85, CiteScore: 2)
Annals of Finance     Hybrid Journal   (Followers: 30, SJR: 0.579, CiteScore: 1)
Annals of Forest Science     Hybrid Journal   (Followers: 7, SJR: 0.986, CiteScore: 2)
Annals of Global Analysis and Geometry     Hybrid Journal   (Followers: 1, SJR: 1.228, CiteScore: 1)
Annals of Hematology     Hybrid Journal   (Followers: 15, SJR: 1.043, CiteScore: 2)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 12, SJR: 0.413, CiteScore: 1)
Annals of Microbiology     Hybrid Journal   (Followers: 11, SJR: 0.479, CiteScore: 2)
Annals of Nuclear Medicine     Hybrid Journal   (Followers: 4, SJR: 0.687, CiteScore: 2)
Annals of Operations Research     Hybrid Journal   (Followers: 10, SJR: 0.943, CiteScore: 2)
Annals of Ophthalmology     Hybrid Journal   (Followers: 11)
Annals of Regional Science     Hybrid Journal   (Followers: 7, SJR: 0.614, CiteScore: 1)
Annals of Software Engineering     Hybrid Journal   (Followers: 13)
Annals of Solid and Structural Mechanics     Hybrid Journal   (Followers: 9, SJR: 0.239, CiteScore: 1)
Annals of Surgical Oncology     Hybrid Journal   (Followers: 13, SJR: 1.986, CiteScore: 4)
Annals of Telecommunications     Hybrid Journal   (Followers: 9, SJR: 0.223, CiteScore: 1)
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1, SJR: 1.495, CiteScore: 1)
Antonie van Leeuwenhoek     Hybrid Journal   (Followers: 5, SJR: 0.834, CiteScore: 2)
Apidologie     Hybrid Journal   (Followers: 4, SJR: 1.22, CiteScore: 3)
APOPTOSIS     Hybrid Journal   (Followers: 8, SJR: 1.424, CiteScore: 4)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2, SJR: 0.294, CiteScore: 1)
Applications of Mathematics     Hybrid Journal   (Followers: 2, SJR: 0.602, CiteScore: 1)
Applied Biochemistry and Biotechnology     Hybrid Journal   (Followers: 43, SJR: 0.571, CiteScore: 2)
Applied Biochemistry and Microbiology     Hybrid Journal   (Followers: 17, SJR: 0.21, CiteScore: 1)
Applied Cancer Research     Open Access  
Applied Categorical Structures     Hybrid Journal   (Followers: 2, SJR: 0.49, CiteScore: 0)
Applied Composite Materials     Hybrid Journal   (Followers: 49, SJR: 0.58, CiteScore: 2)
Applied Entomology and Zoology     Partially Free   (Followers: 4, SJR: 0.422, CiteScore: 1)
Applied Geomatics     Hybrid Journal   (Followers: 3, SJR: 0.733, CiteScore: 3)
Applied Geophysics     Hybrid Journal   (Followers: 8, SJR: 0.488, CiteScore: 1)
Applied Intelligence     Hybrid Journal   (Followers: 12, SJR: 0.6, CiteScore: 2)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 4, SJR: 0.319, CiteScore: 1)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 6, SJR: 0.886, CiteScore: 1)
Applied Mathematics - A J. of Chinese Universities     Hybrid Journal   (SJR: 0.17, CiteScore: 0)
Applied Mathematics and Mechanics     Hybrid Journal   (Followers: 5, SJR: 0.461, CiteScore: 1)
Applied Microbiology and Biotechnology     Hybrid Journal   (Followers: 64, SJR: 1.182, CiteScore: 4)
Applied Physics A     Hybrid Journal   (Followers: 9, SJR: 0.481, CiteScore: 2)
Applied Physics B: Lasers and Optics     Hybrid Journal   (Followers: 24, SJR: 0.74, CiteScore: 2)
Applied Psychophysiology and Biofeedback     Hybrid Journal   (Followers: 8, SJR: 0.519, CiteScore: 2)
Applied Research in Quality of Life     Hybrid Journal   (Followers: 12, SJR: 0.316, CiteScore: 1)
Applied Solar Energy     Hybrid Journal   (Followers: 18, SJR: 0.225, CiteScore: 0)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 5, SJR: 0.542, CiteScore: 1)
Aquaculture Intl.     Hybrid Journal   (Followers: 24, SJR: 0.591, CiteScore: 2)
Aquarium Sciences and Conservation     Hybrid Journal   (Followers: 2)
Aquatic Ecology     Hybrid Journal   (Followers: 34, SJR: 0.656, CiteScore: 2)
Aquatic Geochemistry     Hybrid Journal   (Followers: 4, SJR: 0.591, CiteScore: 1)
Aquatic Sciences     Hybrid Journal   (Followers: 13, SJR: 1.109, CiteScore: 3)
Arabian J. for Science and Engineering     Hybrid Journal   (Followers: 5, SJR: 0.303, CiteScore: 1)
Arabian J. of Geosciences     Hybrid Journal   (Followers: 2, SJR: 0.319, CiteScore: 1)
Archaeological and Anthropological Sciences     Hybrid Journal   (Followers: 20, SJR: 1.052, CiteScore: 2)
Archaeologies     Hybrid Journal   (Followers: 12, SJR: 0.224, CiteScore: 0)
Archiv der Mathematik     Hybrid Journal   (Followers: 1, SJR: 0.725, CiteScore: 1)
Archival Science     Hybrid Journal   (Followers: 60, SJR: 0.745, CiteScore: 2)
Archive for History of Exact Sciences     Hybrid Journal   (Followers: 7, SJR: 0.186, CiteScore: 1)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 3, SJR: 0.909, CiteScore: 1)
Archive for Rational Mechanics and Analysis     Hybrid Journal   (SJR: 3.93, CiteScore: 3)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 5, SJR: 0.79, CiteScore: 2)
Archives and Museum Informatics     Hybrid Journal   (Followers: 144, SJR: 0.101, CiteScore: 0)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 5, SJR: 1.41, CiteScore: 5)
Archives of Dermatological Research     Hybrid Journal   (Followers: 7, SJR: 1.006, CiteScore: 2)
Archives of Environmental Contamination and Toxicology     Hybrid Journal   (Followers: 14, SJR: 0.773, CiteScore: 2)
Archives of Gynecology and Obstetrics     Hybrid Journal   (Followers: 16, SJR: 0.956, CiteScore: 2)
Archives of Microbiology     Hybrid Journal   (Followers: 8, SJR: 0.644, CiteScore: 2)
Archives of Orthopaedic and Trauma Surgery     Hybrid Journal   (Followers: 8, SJR: 1.146, CiteScore: 2)
Archives of Osteoporosis     Hybrid Journal   (Followers: 2, SJR: 0.71, CiteScore: 2)
Archives of Sexual Behavior     Hybrid Journal   (Followers: 10, SJR: 1.493, CiteScore: 3)
Archives of Toxicology     Hybrid Journal   (Followers: 17, SJR: 1.541, CiteScore: 5)
Archives of Virology     Hybrid Journal   (Followers: 5, SJR: 0.973, CiteScore: 2)
Archives of Women's Mental Health     Hybrid Journal   (Followers: 14, SJR: 1.274, CiteScore: 3)
Archivio di Ortopedia e Reumatologia     Hybrid Journal  
Archivum Immunologiae et Therapiae Experimentalis     Hybrid Journal   (Followers: 2, SJR: 0.946, CiteScore: 3)
ArgoSpine News & J.     Hybrid Journal  
Argumentation     Hybrid Journal   (Followers: 6, SJR: 0.349, CiteScore: 1)
Arid Ecosystems     Hybrid Journal   (Followers: 2, SJR: 0.2, CiteScore: 0)
Arkiv för Matematik     Hybrid Journal   (Followers: 1, SJR: 0.766, CiteScore: 1)
Arnold Mathematical J.     Hybrid Journal   (Followers: 1, SJR: 0.355, CiteScore: 0)
Arthropod-Plant Interactions     Hybrid Journal   (Followers: 2, SJR: 0.839, CiteScore: 2)
Arthroskopie     Hybrid Journal   (Followers: 1, SJR: 0.131, CiteScore: 0)
Artificial Intelligence and Law     Hybrid Journal   (Followers: 11, SJR: 0.937, CiteScore: 2)
Artificial Intelligence Review     Hybrid Journal   (Followers: 15, SJR: 0.833, CiteScore: 4)
Artificial Life and Robotics     Hybrid Journal   (Followers: 9, SJR: 0.226, CiteScore: 0)
Asia Europe J.     Hybrid Journal   (Followers: 5, SJR: 0.504, CiteScore: 1)
Asia Pacific Education Review     Hybrid Journal   (Followers: 12, SJR: 0.479, CiteScore: 1)
Asia Pacific J. of Management     Hybrid Journal   (Followers: 16, SJR: 1.185, CiteScore: 2)
Asia-Pacific Education Researcher     Hybrid Journal   (Followers: 12, SJR: 0.353, CiteScore: 1)
Asia-Pacific Financial Markets     Hybrid Journal   (Followers: 2, SJR: 0.187, CiteScore: 0)
Asia-Pacific J. of Atmospheric Sciences     Hybrid Journal   (Followers: 19, SJR: 0.855, CiteScore: 1)
Asian Business & Management     Hybrid Journal   (Followers: 9, SJR: 0.378, CiteScore: 1)
Asian J. of Business Ethics     Hybrid Journal   (Followers: 9)
Asian J. of Criminology     Hybrid Journal   (Followers: 6, SJR: 0.543, CiteScore: 1)
AStA Advances in Statistical Analysis     Hybrid Journal   (Followers: 3, SJR: 0.548, CiteScore: 1)
AStA Wirtschafts- und Sozialstatistisches Archiv     Hybrid Journal   (Followers: 5, SJR: 0.183, CiteScore: 0)
ästhetische dermatologie & kosmetologie     Full-text available via subscription  

        1 2 3 4 5 6 7 8 | Last   [Sort by number of followers]   [Restore default list]

Journal Cover
Journal Prestige (SJR): 0.56
Citation Impact (citeScore): 1
Number of Followers: 9  
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1432-0541 - ISSN (Online) 0178-4617
Published by Springer-Verlag Homepage  [2350 journals]
  • Approximation Algorithms for the Max-Buying Problem with Limited Supply
    • Authors: Cristina G. Fernandes; Rafael C. S. Schouery
      Pages: 2973 - 2992
      Abstract: Abstract We consider the Max-Buying Problem with Limited Supply, in which there are n items, with  \(C_i\) copies of each item i, and m consumers such that each consumer b has a valuation \(v_{ib}\) for item i. The goal is to find a pricing p and an allocation of items to consumers that maximize the revenue, with every item allocated to at most \(C_i\) consumers, every consumer receives at most one item, and if a consumer b receives item i, then \(p_i \le v_{ib}\) . We present a randomized \(e/(e-1)\) -approximation for the Max-Buying Problem with Limited Supply and show how to derandomize it, improving the previously known upper bound of 2. The algorithm uses an integer programming formulation with an exponential number of variables to do a probabilistic rounding and it explores some structure of the problem that might be useful when developing approximations for other pricing problems. We also present a PTAS for the price ladder variant, in which the pricing must be non-increasing (that is, \(p_1 \ge p_2 \ge \cdots \ge p_n\) ), improving the previously known upper bound of 4.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0364-7
      Issue No: Vol. 80, No. 11 (2018)
  • On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic
           Network Problems
    • Authors: Leo van Iersel; Steven Kelk; Georgios Stamoulis; Leen Stougie; Olivier Boes
      Pages: 2993 - 3022
      Abstract: Abstract The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0366-5
      Issue No: Vol. 80, No. 11 (2018)
  • A Faster Exact-Counting Protocol for Anonymous Dynamic Networks
    • Authors: Maitri Chakraborty; Alessia Milani; Miguel A. Mosteiro
      Pages: 3023 - 3049
      Abstract: Abstract We study the problem of Counting the number of nodes in Anonymous Dynamic Network: nodes do not have identifiers and the network topology changes frequently. Counting is a fundamental task in distributed computing, for instance, to decide termination. Knowing what is the cost of anonymity is of paramount importance to understand what is feasible for future generations of Dynamic Networks, where the lack of nodes identifiers might facilitate mass production. Previous upper bounds to compute the exact network size are double-exponential. Strikingly, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this work, we achieve an exponential speedup presenting Incremental Counting (IC), a distributed Counting protocol for Anonymous Dynamic Networks that has exponential time complexity and computes the exact size of the system. We complement the theoretical study evaluating IC experimentally. We tested a variety of network topologies that may appear in practice, including extremal cases such as trees, paths, and continuously changing topologies. Our simulations showed that IC is polynomial for all the inputs tested, paving the way to use it in practical applications where the network topology is predictable.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0367-4
      Issue No: Vol. 80, No. 11 (2018)
  • Bounded-Hop Communication Networks
    • Authors: Paz Carmi; Lilach Chaitman-Yerushalmi; Ohad Trabelsi
      Pages: 3050 - 3077
      Abstract: Abstract We study the problem of assigning transmission ranges to radio stations in the plane such that any pair of stations can communicate within a bounded number of hops h and the cost of the network is minimized. We consider two settings of the problem: collinear station locations and arbitrary locations. For the case of collinear stations, we introduce the pioneer polynomial-time exact algorithm for any \(\alpha \ge 1\) and constant h, and thus conclude that the 1D version of the problem, where h is a constant, is in \(\mathcal {P}\) . Furthermore, we provide a 3 / 2-approximation algorithm for the case where h is an arbitrary number and \(\alpha =1\) , improving the previously best known approximation ratio of 2. For the case of stations placed arbitrarily in the plane and \(\alpha =1\) , we first present a \((1.5+ \varepsilon )\) -approximation algorithm for a case where a deviation of one hop ( \(h+1\) hops in total) is acceptable. Then, we show a \((3+\varepsilon )\) -approximation algorithm that complies with the exact hop bound. To achieve that, we introduce the following two auxiliary problems, which are of independent interest. The first is the bounded-hop multi-sink range problem, for which we present a PTAS which can be applied to compute a \((1+\varepsilon )\) -approximation for the bounded diameter minimum spanning tree, for any \(\varepsilon >0\) . The second auxiliary problem is the bounded-hop dual-sink pruning problem, for which we show a polynomial-time algorithm. To conclude, we consider the initial bounded-hop all-to-all range assignment problem and show that a combined application of the aforementioned problems yields the \((3+\varepsilon )\) -approximation ratio for this problem, which improves the previously best known approximation ratio of \(4(9^{h-2})/(\root h \of {2}-1)\) .
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0370-9
      Issue No: Vol. 80, No. 11 (2018)
  • Metastability of Logit Dynamics for Coordination Games
    • Authors: Vincenzo Auletta; Diodato Ferraioli; Francesco Pasquale; Giuseppe Persiano
      Pages: 3078 - 3131
      Abstract: Abstract Logit dynamics (Blume in Games Econ Behav 5:387–424, 1993) are randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. It can happen that the chain is “metastable”, i.e., on a time-scale shorter than the mixing time, it stays close to some probability distribution over the state space, while in a time-scale multiple of the mixing time it jumps from one distribution to another. In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the logit dynamics for some classes of coordination games. We first consider a pure n-player coordination game that highlights the distinctive features of our metastability notion based on distributions. Then, we study coordination games on the clique without a risk-dominant strategy (which are equivalent to the well-known Glauber dynamics for the Curie–Weiss model) and coordination games on a ring (both with and without risk-dominant strategy).
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0371-8
      Issue No: Vol. 80, No. 11 (2018)
  • Approximation Schemes for Stochastic Mean Payoff Games with Perfect
           Information and Few Random Positions
    • Authors: Endre Boros; Khaled Elbassioni; Mahmoud Fouz; Vladimir Gurvich; Kazuhisa Makino; Bodo Manthey
      Pages: 3132 - 3157
      Abstract: Abstract We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0372-7
      Issue No: Vol. 80, No. 11 (2018)
  • Algorithms for Communication Scheduling in Data Gathering Network with
           Data Compression
    • Authors: Wenchang Luo; Yao Xu; Boyuan Gu; Weitian Tong; Randy Goebel; Guohui Lin
      Pages: 3158 - 3176
      Abstract: Abstract We consider a communication scheduling problem that arises within wireless sensor networks, where data is accumulated by the sensors and transferred directly to a central base station. One may choose to compress the data collected by a sensor, to decrease the data size for transmission, but the cost of compression must be considered. The goal is to designate a subset of sensors to compress their collected data, and then to determine a data transmission order for all the sensors, such that the total compression cost is minimized subject to a bounded data transmission completion time (a.k.a. makespan). A recent result confirms the NP-hardness for this problem, even in the special case where data compression is free. Here we first design a pseudo-polynomial time exact algorithm, articulated within a dynamic programming scheme. This algorithm also solves a variant with the complementary optimization goal—to minimize the makespan while constraining the total compression cost within a given budget. Our second result consists of a bi-factor \((1 + \epsilon , 2)\) -approximation for the problem, where \((1 + \epsilon )\) refers to the compression cost and 2 refers to the makespan, and a 2-approximation for the variant. Lastly, we apply a sparsing technique to the dynamic programming exact algorithm, to achieve a dual fully polynomial time approximation scheme for the problem and a usual fully polynomial time approximation scheme for the variant.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0373-6
      Issue No: Vol. 80, No. 11 (2018)
  • Spanning Trees in Multipartite Geometric Graphs
    • Authors: Ahmad Biniaz; Prosenjit Bose; David Eppstein; Anil Maheshwari; Pat Morin; Michiel Smid
      Pages: 3177 - 3191
      Abstract: Abstract Let R and B be two disjoint sets of points in the plane where the points of R are colored red and the points of B are colored blue, and let \(n= R\cup B \) . A bichromatic spanning tree is a spanning tree in the complete bipartite geometric graph with bipartition (R, B). The minimum (respectively maximum) bichromatic spanning tree problem is the problem of computing a bichromatic spanning tree of minimum (respectively maximum) total edge length. (1) We present a simple algorithm that solves the minimum bichromatic spanning tree problem in \(O(n\log ^3 n)\) time. This algorithm can easily be extended to solve the maximum bichromatic spanning tree problem within the same time bound. It also can easily be generalized to multicolored point sets. (2) We present \(\Theta (n\log n)\) -time algorithms that solve the minimum and the maximum bichromatic spanning tree problems. (3) We extend the bichromatic spanning tree algorithms and solve the multicolored version of these problems in \(O(n\log n\log k)\) time, where k is the number of different colors (or the size of the multipartition in a complete multipartite geometric graph).
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0375-4
      Issue No: Vol. 80, No. 11 (2018)
  • Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges
    • Authors: Peyman Afshani; Konstantinos Tsakalidis
      Pages: 3192 - 3206
      Abstract: Abstract Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in \(O\left( n\log n\right) \) worst-case time, using \(O\left( n\right) \) space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matoušek (Comput Geom 2(3):169–186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912–953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866–881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0376-3
      Issue No: Vol. 80, No. 11 (2018)
  • Dynamic Relative Compression, Dynamic Partial Sums, and Substring
    • Authors: Philip Bille; Anders Roy Christiansen; Patrick Hagge Cording; Inge Li Gørtz; Frederik Rye Skjoldjensen; Hjalte Wedel Vildhøj; Søren Vind
      Pages: 3207 - 3224
      Abstract: Abstract Given a static reference string R and a source string S, a relative compression of S with respect to R is an encoding of S as a sequence of references to substrings of R. Relative compression schemes are a classic model of compression and have recently proved very successful for compressing highly-repetitive massive data sets such as genomes and web-data. We initiate the study of relative compression in a dynamic setting where the compressed source string S is subject to edit operations. The goal is to maintain the compressed representation compactly, while supporting edits and allowing efficient random access to the (uncompressed) source string. We present new data structures that achieve optimal time for updates and queries while using space linear in the size of the optimal relative compression, for nearly all combinations of parameters. We also present solutions for restricted and extended sets of updates. To achieve these results, we revisit the dynamic partial sums problem and the substring concatenation problem. We present new optimal or near optimal bounds for these problems. Plugging in our new results we also immediately obtain new bounds for the string indexing for patterns with wildcards problem and the dynamic text and static pattern matching problem.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0380-7
      Issue No: Vol. 80, No. 11 (2018)
  • Improved Bounds in Stochastic Matching and Optimization
    • Authors: Alok Baveja; Amit Chavan; Andrei Nikiforov; Aravind Srinivasan; Pan Xu
      Pages: 3225 - 3252
      Abstract: Abstract Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the current-best approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: Algorithms-ESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733–762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linear-programming relaxations of these problems.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0383-4
      Issue No: Vol. 80, No. 11 (2018)
  • Finding Pairwise Intersections Inside a Query Range
    • Authors: Mark de Berg; Joachim Gudmundsson; Ali D. Mehrabi
      Pages: 3253 - 3269
      Abstract: Abstract We study the following problem: preprocess a set \(\mathcal {O}\) of objects into a data structure that allows us to efficiently report all pairs of objects from \(\mathcal {O}\) that intersect inside an axis-aligned query range \({Q}\) . We present data structures of size \(O(n\cdot {{\mathrm{polylog\,}}}n)\) and with query time \(O((k+1)\cdot {{\mathrm{polylog\,}}}n)\) time, where k is the number of reported pairs, for two classes of objects in \({\mathbb R}^2\) : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in  \({\mathbb R}^3\) , we present a data structure of size \(O(n\sqrt{n}\cdot {{\mathrm{polylog\,}}}n)\) and query time \(O((\sqrt{n}+k)\cdot {{\mathrm{polylog\,}}}n)\) . When the objects and query are fat, we obtain \(O((k+1)\cdot {{\mathrm{polylog\,}}}n)\) query time using \(O(n\cdot {{\mathrm{polylog\,}}}n)\) storage.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0384-3
      Issue No: Vol. 80, No. 11 (2018)
  • Approximation Algorithms for Highly Connected Multi-dominating Sets in
           Unit Disk Graphs
    • Authors: Takuro Fukunaga
      Pages: 3270 - 3292
      Abstract: Abstract Given an undirected graph on a node set V and positive integers k and m, a k-connected m-dominating set ((k, m)-CDS) is defined as a subset S of V such that each node in \(V{\setminus }S\) has at least m neighbors in S, and a k-connected subgraph is induced by S. The weighted (k, m)-CDS problem is to find a minimum weight (k, m)-CDS in a given node-weighted graph. The problem is called the unweighted (k, m)-CDS problem if the objective is to minimize the cardinality of a (k, m)-CDS. These problems have been actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in a wireless ad hoc network. In this paper, we consider the case in which \(k \le m\) , and we present a simple \(O(k5^k)\) -approximation algorithm for the unweighted (k, m)-CDS problem, and a primal-dual \(O(k^2 \log k)\) -approximation algorithm for the weighted (k, m)-CDS problem.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0385-2
      Issue No: Vol. 80, No. 11 (2018)
  • Batch Coloring of Graphs
    • Authors: Joan Boyar; Leah Epstein; Lene M. Favrholdt; Kim S. Larsen; Asaf Levin
      Pages: 3293 - 3315
      Abstract: Abstract We study two versions of graph coloring, where the goal is to assign a positive integer color to each vertex of an input graph such that adjacent vertices do not receive the same color assignment. For classic vertex coloring, the goal is to minimize the maximum color used, and for the sum coloring problem, the goal is to minimize the sum of colors assigned to all input vertices. In the offline variant, the entire graph is presented at once, and in online problems, one vertex is presented for coloring at each time, and the only information is the identity of its neighbors among previously known vertices. In batched graph coloring, vertices are presented in k batches, for a fixed integer \(k \ge 2\) , such that the vertices of a batch are presented as a set, and must be colored before the vertices of the next batch are presented. This last model is an intermediate model, which bridges between the two extreme scenarios of the online and offline models. We provide several results, including a general result for sum coloring and results for the classic graph coloring problem on restricted graph classes: We show tight bounds for any graph class containing trees as a subclass (forests, bipartite graphs, planar graphs, and perfect graphs, for example), and an interesting result for interval graphs and \(k=2\) , where the value of the (strict and asymptotic) competitive ratio depends on whether the graph is presented with its interval representation or not.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0386-1
      Issue No: Vol. 80, No. 11 (2018)
  • Data Structures for Halfplane Proximity Queries and Incremental Voronoi
    • Authors: Boris Aronov; Prosenjit Bose; Erik D. Demaine; Joachim Gudmundsson; John Iacono; Stefan Langerman; Michiel Smid
      Pages: 3316 - 3334
      Abstract: Abstract We consider preprocessing a set S of n points in convex position in the plane into a data structure supporting queries of the following form: given a point q and a directed line  \(\ell \) in the plane, report the point of S that is farthest from (or, alternatively, nearest to) the point q among all points to the left of line  \(\ell \) . We present two data structures for this problem. The first data structure uses \(O(n^{1+\varepsilon })\) space and preprocessing time, and answers queries in \(O(2^{1/\varepsilon }\log n)\) time, for any \(0< \varepsilon < 1\) . The second data structure uses \(O(n \log ^3 n)\) space and polynomial preprocessing time, and answers queries in \(O(\log n)\) time. These are the first solutions to the problem with \(O(\log n)\) query time and \(o(n^2)\) space. The second data structure uses a new representation of nearest- and farthest-point Voronoi diagrams of points in convex position. This representation supports the insertion of new points in clockwise order using only \(O(\log n)\) amortized pointer changes, in addition to \(O(\log n)\) -time point-location queries, even though every such update may make \(\Theta (n)\) combinatorial changes to the Voronoi diagram. This data structure is the first demonstration that deterministically and incrementally constructed Voronoi diagrams can be maintained in o(n) amortized pointer changes per operation while keeping \(O(\log n)\) -time point-location queries.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0389-y
      Issue No: Vol. 80, No. 11 (2018)
  • Online Constrained Forest and Prize-Collecting Network Design
    • Authors: Jiawei Qian; Seeun William Umboh; David P. Williamson
      Pages: 3335 - 3364
      Abstract: Abstract In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berman and Coulston (Proceedings of the 29th annual ACM symposium on theory of computing, pp 344–353, 1997) and one for (offline) general network design problems due to Goemans and Williamson (SIAM J Comput 24:296–317, 1995); we give an \(O(\log k)\) -competitive algorithm, where k is the number of nodes that must be connected. We also consider a further generalization of the problem that allows us to pay penalties in exchange for violating connectivity constraints; we give an online \(O(\log k)\) -competitive algorithm for this case as well.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0391-4
      Issue No: Vol. 80, No. 11 (2018)
  • Building Fences Straight and High: An Optimal Algorithm for Finding the
           Maximum Length You Can Cut k Times from Given Sticks
    • Authors: Raphael Reitzig; Sebastian Wild
      Pages: 3365 - 3396
      Abstract: Abstract Given a set of n sticks of various (not necessarily different) lengths, what is the largest length so that we can cut k equally long pieces of this length from the given set of sticks' We analyze the structure of this problem and show that it essentially reduces to a single call of a selection algorithm; we thus obtain an optimal linear-time algorithm. This algorithm also solves the related envy-free stick-division problem, which Segal-Halevi et al. (ACM Trans Algorithms 13(1):1–32, 2016. ISSN: 15496325. recently used as their central primitive operation for the first discrete and bounded envy-free cake cutting protocol with a proportionality guarantee when pieces can be put to waste.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0392-3
      Issue No: Vol. 80, No. 11 (2018)
  • De-anonymization of Heterogeneous Random Graphs in Quasilinear Time
    • Authors: Karl Bringmann; Tobias Friedrich; Anton Krohmer
      Pages: 3397 - 3427
      Abstract: Abstract There are hundreds of online social networks with altogether billions of users. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy—it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an n-vertex graph, our algorithm uses \(n^\varepsilon \) seed nodes (for an arbitrarily small  \(\varepsilon \) ) and runs in quasilinear time. This improves previous theoretical results which need \(\Theta (n)\) seed nodes and have runtimes of order \(n^{1+\Omega (1)}\) . Additionally, the applicability of our algorithm is studied experimentally on different networks.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-017-0395-0
      Issue No: Vol. 80, No. 11 (2018)
  • Correction to: Trading Off Worst and Expected Cost in Decision Tree
    • Authors: Aline Saettler; Eduardo Laber; Ferdinando Cicalese
      Pages: 3431 - 3436
      Abstract: Abstract This erratum fixes a technical problem in the paper published in Algorithmica, Volume 79, Number 3, November 2017, pp. 886–908. Theorem 1 of this paper gives upper bounds on both worst testing cost and expected testing cost of the decision tree built by Algorithm 1.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-018-0423-8
      Issue No: Vol. 80, No. 11 (2018)
  • Correction to: A Connection Between Sports and Matroids: How Many Teams
           Can We Beat'
    • Abstract: Abstract The authors regret the following error in their article “A connection between sports and matroids: How many teams can we beat'” (Algorithmica, doi: 10.1007/s00453-016-0256-2), considering the computational complexity of the problem MinStanding(S). In Theorem 3 of our paper [4], we erroneously claimed a \(\mathsf {W}[1]\) -hardness result to hold even for the case where the undirected version of the input graph is claw-free. In fact, we can only prove the theorem for \(K_{1,4}\) -free graphs, so the property claw-free should have been replaced by the property \(K_{1,4}\) -free.
      PubDate: 2018-11-01
      DOI: 10.1007/s00453-016-0256-2) considering the computational complexity of the problem
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
Home (Search)
Subjects A-Z
Publishers A-Z
Your IP address:
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-