for Journals by Title or ISSN
for Articles by Keywords

Publisher: Springer-Verlag   (Total: 2353 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 2353 Journals sorted alphabetically
3D Research     Hybrid Journal   (Followers: 19, SJR: 0.214, h-index: 10)
4OR: A Quarterly J. of Operations Research     Hybrid Journal   (Followers: 9, SJR: 1.073, h-index: 25)
AAPS J.     Hybrid Journal   (Followers: 20, SJR: 1.192, h-index: 74)
AAPS PharmSciTech     Hybrid Journal   (Followers: 6, SJR: 0.718, h-index: 54)
Abdominal Imaging     Hybrid Journal   (Followers: 14, SJR: 0.723, h-index: 60)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 2, SJR: 0.447, h-index: 12)
Academic Psychiatry     Full-text available via subscription   (Followers: 22, SJR: 0.492, h-index: 32)
Academic Questions     Hybrid Journal   (Followers: 7, SJR: 0.135, h-index: 6)
Accreditation and Quality Assurance: J. for Quality, Comparability and Reliability in Chemical Measurement     Hybrid Journal   (Followers: 26, SJR: 0.378, h-index: 30)
Acoustical Physics     Hybrid Journal   (Followers: 11, SJR: 0.355, h-index: 20)
Acoustics Australia     Hybrid Journal  
Acta Analytica     Hybrid Journal   (Followers: 7, SJR: 0.387, h-index: 6)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1, SJR: 0.624, h-index: 34)
Acta Biotheoretica     Hybrid Journal   (Followers: 5, SJR: 0.419, h-index: 25)
Acta Diabetologica     Hybrid Journal   (Followers: 14, SJR: 1.318, h-index: 46)
Acta Endoscopica     Hybrid Journal   (Followers: 1, SJR: 0.113, h-index: 8)
acta ethologica     Hybrid Journal   (Followers: 4, SJR: 0.465, h-index: 23)
Acta Geochimica     Hybrid Journal   (Followers: 4)
Acta Geodaetica et Geophysica     Hybrid Journal   (Followers: 1, SJR: 0.294, h-index: 13)
Acta Geotechnica     Hybrid Journal   (Followers: 7, SJR: 1.818, h-index: 22)
Acta Informatica     Hybrid Journal   (Followers: 5, SJR: 0.524, h-index: 32)
Acta Mathematica     Hybrid Journal   (Followers: 11, SJR: 8.021, h-index: 47)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2, SJR: 0.53, h-index: 29)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 5, SJR: 0.406, h-index: 30)
Acta Mathematica Vietnamica     Hybrid Journal   (SJR: 0.451, h-index: 5)
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal   (SJR: 0.22, h-index: 20)
Acta Mechanica     Hybrid Journal   (Followers: 19, SJR: 0.898, h-index: 52)
Acta Mechanica Sinica     Hybrid Journal   (Followers: 5, SJR: 0.426, h-index: 29)
Acta Metallurgica Sinica (English Letters)     Hybrid Journal   (Followers: 5, SJR: 0.525, h-index: 18)
Acta Meteorologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.524, h-index: 14)
Acta Neurochirurgica     Hybrid Journal   (Followers: 6, SJR: 0.833, h-index: 73)
Acta Neurologica Belgica     Hybrid Journal   (SJR: 0.348, h-index: 27)
Acta Neuropathologica     Hybrid Journal   (Followers: 5, SJR: 6.61, h-index: 117)
Acta Oceanologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.295, h-index: 17)
Acta Parasitologica     Hybrid Journal   (Followers: 9, SJR: 0.581, h-index: 28)
Acta Physiologiae Plantarum     Hybrid Journal   (Followers: 2, SJR: 0.551, h-index: 39)
Acta Politica     Hybrid Journal   (Followers: 13, SJR: 0.658, h-index: 20)
Activitas Nervosa Superior     Hybrid Journal  
adhäsion KLEBEN & DICHTEN     Hybrid Journal   (Followers: 5, SJR: 0.103, h-index: 4)
ADHD Attention Deficit and Hyperactivity Disorders     Hybrid Journal   (Followers: 20, SJR: 0.871, h-index: 15)
Adhesion Adhesives & Sealants     Hybrid Journal   (Followers: 7)
Administration and Policy in Mental Health and Mental Health Services Research     Partially Free   (Followers: 15, SJR: 0.795, h-index: 40)
Adsorption     Hybrid Journal   (Followers: 4, SJR: 0.774, h-index: 52)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 3, SJR: 0.319, h-index: 15)
Advances in Atmospheric Sciences     Hybrid Journal   (Followers: 34, SJR: 0.959, h-index: 44)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15, SJR: 1.255, h-index: 44)
Advances in Contraception     Hybrid Journal   (Followers: 3)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 54, SJR: 1.113, h-index: 14)
Advances in Gerontology     Partially Free   (Followers: 9, SJR: 0.141, h-index: 3)
Advances in Health Sciences Education     Hybrid Journal   (Followers: 22, SJR: 1.397, h-index: 42)
Advances in Manufacturing     Hybrid Journal   (Followers: 3, SJR: 0.2, h-index: 4)
Advances in Polymer Science     Hybrid Journal   (Followers: 41, SJR: 0.637, h-index: 89)
Advances in Therapy     Hybrid Journal   (Followers: 5, SJR: 0.79, h-index: 44)
Aegean Review of the Law of the Sea and Maritime Law     Hybrid Journal   (Followers: 7)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2, SJR: 0.882, h-index: 23)
Aerobiologia     Hybrid Journal   (Followers: 1, SJR: 0.511, h-index: 36)
Aesthetic Plastic Surgery     Hybrid Journal   (Followers: 9, SJR: 0.821, h-index: 49)
African Archaeological Review     Hybrid Journal   (Followers: 15, SJR: 0.612, h-index: 24)
Afrika Matematika     Hybrid Journal   (Followers: 1, SJR: 0.248, h-index: 6)
AGE     Hybrid Journal   (Followers: 7, SJR: 1.358, h-index: 33)
Ageing Intl.     Hybrid Journal   (Followers: 7, SJR: 0.337, h-index: 10)
Aggiornamenti CIO     Hybrid Journal   (Followers: 1)
Aging Clinical and Experimental Research     Hybrid Journal   (Followers: 3, SJR: 0.529, h-index: 55)
Agricultural Research     Hybrid Journal   (Followers: 3)
Agriculture and Human Values     Hybrid Journal   (Followers: 12, SJR: 1.197, h-index: 49)
Agroforestry Systems     Hybrid Journal   (Followers: 20, SJR: 0.64, h-index: 56)
Agronomy for Sustainable Development     Hybrid Journal   (Followers: 10, SJR: 1.732, h-index: 59)
AI & Society     Hybrid Journal   (Followers: 7, SJR: 0.171, h-index: 19)
AIDS and Behavior     Hybrid Journal   (Followers: 13, SJR: 2.006, h-index: 71)
Air Quality, Atmosphere & Health     Hybrid Journal   (Followers: 3, SJR: 0.706, h-index: 19)
Akupunktur & Aurikulomedizin     Full-text available via subscription   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 3, SJR: 0.566, h-index: 18)
Algebra Universalis     Hybrid Journal   (Followers: 2, SJR: 0.388, h-index: 22)
Algebras and Representation Theory     Hybrid Journal   (Followers: 1, SJR: 0.868, h-index: 20)
Algorithmica     Hybrid Journal   (Followers: 7, SJR: 0.898, h-index: 56)
Allergo J.     Full-text available via subscription   (Followers: 1, SJR: 0.183, h-index: 20)
Allergo J. Intl.     Hybrid Journal   (Followers: 2)
Alpine Botany     Hybrid Journal   (Followers: 4, SJR: 0.729, h-index: 20)
ALTEX : Alternatives to Animal Experimentation     Open Access   (Followers: 3, SJR: 1.392, h-index: 32)
AMBIO     Hybrid Journal   (Followers: 15, SJR: 1.094, h-index: 87)
American J. of Cardiovascular Drugs     Hybrid Journal   (Followers: 13, SJR: 0.864, h-index: 39)
American J. of Community Psychology     Hybrid Journal   (Followers: 23, SJR: 1.237, h-index: 83)
American J. of Criminal Justice     Hybrid Journal   (Followers: 6, SJR: 0.634, h-index: 13)
American J. of Cultural Sociology     Hybrid Journal   (Followers: 11, SJR: 0.283, h-index: 3)
American J. of Dance Therapy     Hybrid Journal   (Followers: 4, SJR: 0.175, h-index: 13)
American J. of Potato Research     Hybrid Journal   (Followers: 2, SJR: 0.558, h-index: 35)
American J. of Psychoanalysis     Hybrid Journal   (Followers: 21, SJR: 0.293, h-index: 13)
American Sociologist     Hybrid Journal   (Followers: 12, SJR: 0.18, h-index: 13)
Amino Acids     Hybrid Journal   (Followers: 8, SJR: 1.362, h-index: 83)
AMS Review     Partially Free   (Followers: 4)
Analog Integrated Circuits and Signal Processing     Hybrid Journal   (Followers: 5, SJR: 0.21, h-index: 37)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 3, SJR: 0.665, h-index: 7)
Analysis in Theory and Applications     Hybrid Journal   (Followers: 1)
Analysis of Verbal Behavior     Hybrid Journal   (Followers: 5)
Analytical and Bioanalytical Chemistry     Hybrid Journal   (Followers: 28, SJR: 1.096, h-index: 123)
Anatomical Science Intl.     Hybrid Journal   (Followers: 2, SJR: 0.301, h-index: 26)
Angewandte Schmerztherapie und Palliativmedizin     Hybrid Journal  
Angiogenesis     Hybrid Journal   (Followers: 3, SJR: 2.212, h-index: 69)
Animal Cognition     Hybrid Journal   (Followers: 16, SJR: 1.122, h-index: 55)
Annales françaises de médecine d'urgence     Hybrid Journal   (Followers: 1, SJR: 0.156, h-index: 4)
Annales Henri Poincaré     Hybrid Journal   (Followers: 3, SJR: 1.377, h-index: 32)
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4)
Annali dell'Universita di Ferrara     Hybrid Journal   (SJR: 0.504, h-index: 14)
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1, SJR: 1.167, h-index: 26)
Annals of Behavioral Medicine     Hybrid Journal   (Followers: 11, SJR: 2.112, h-index: 98)
Annals of Biomedical Engineering     Hybrid Journal   (Followers: 18, SJR: 1.182, h-index: 94)
Annals of Combinatorics     Hybrid Journal   (Followers: 3, SJR: 0.849, h-index: 15)
Annals of Data Science     Hybrid Journal   (Followers: 9)
Annals of Dyslexia     Hybrid Journal   (Followers: 9, SJR: 0.857, h-index: 40)
Annals of Finance     Hybrid Journal   (Followers: 28, SJR: 0.686, h-index: 14)
Annals of Forest Science     Hybrid Journal   (Followers: 4, SJR: 0.929, h-index: 57)
Annals of Global Analysis and Geometry     Hybrid Journal   (Followers: 1, SJR: 1.136, h-index: 23)
Annals of Hematology     Hybrid Journal   (Followers: 14, SJR: 1.117, h-index: 62)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 6, SJR: 0.593, h-index: 42)
Annals of Microbiology     Hybrid Journal   (Followers: 10, SJR: 0.402, h-index: 26)
Annals of Nuclear Medicine     Hybrid Journal   (Followers: 5, SJR: 0.68, h-index: 45)
Annals of Operations Research     Hybrid Journal   (Followers: 8, SJR: 1.186, h-index: 78)
Annals of Ophthalmology     Hybrid Journal   (Followers: 10)
Annals of Regional Science     Hybrid Journal   (Followers: 7, SJR: 0.405, h-index: 42)
Annals of Software Engineering     Hybrid Journal   (Followers: 12)
Annals of Solid and Structural Mechanics     Hybrid Journal   (Followers: 10, SJR: 0.553, h-index: 8)
Annals of Surgical Oncology     Hybrid Journal   (Followers: 13, SJR: 1.902, h-index: 127)
Annals of Telecommunications     Hybrid Journal   (Followers: 7, SJR: 0.315, h-index: 25)
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1, SJR: 0.931, h-index: 31)
Antonie van Leeuwenhoek     Hybrid Journal   (Followers: 5, SJR: 0.992, h-index: 87)
Apidologie     Hybrid Journal   (Followers: 4, SJR: 1.14, h-index: 57)
APOPTOSIS     Hybrid Journal   (Followers: 8, SJR: 1.554, h-index: 87)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2, SJR: 0.354, h-index: 27)
Applications of Mathematics     Hybrid Journal   (Followers: 1, SJR: 0.274, h-index: 20)
Applied Biochemistry and Biotechnology     Hybrid Journal   (Followers: 44, SJR: 0.575, h-index: 80)
Applied Biochemistry and Microbiology     Hybrid Journal   (Followers: 17, SJR: 0.267, h-index: 26)
Applied Cancer Research     Open Access  
Applied Categorical Structures     Hybrid Journal   (Followers: 2, SJR: 0.361, h-index: 21)
Applied Composite Materials     Hybrid Journal   (Followers: 48, SJR: 0.705, h-index: 35)
Applied Entomology and Zoology     Partially Free   (Followers: 2, SJR: 0.554, h-index: 34)
Applied Geomatics     Hybrid Journal   (Followers: 3, SJR: 0.323, h-index: 9)
Applied Geophysics     Hybrid Journal   (Followers: 8, SJR: 0.541, h-index: 13)
Applied Intelligence     Hybrid Journal   (Followers: 12, SJR: 0.777, h-index: 43)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 4, SJR: 0.358, h-index: 34)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 4, SJR: 0.955, h-index: 33)
Applied Mathematics - A J. of Chinese Universities     Hybrid Journal   (SJR: 0.275, h-index: 8)
Applied Mathematics and Mechanics     Hybrid Journal   (Followers: 4, SJR: 0.37, h-index: 26)
Applied Microbiology and Biotechnology     Hybrid Journal   (Followers: 62, SJR: 1.262, h-index: 161)
Applied Physics A     Hybrid Journal   (Followers: 7, SJR: 0.535, h-index: 121)
Applied Physics B: Lasers and Optics     Hybrid Journal   (Followers: 23, SJR: 0.983, h-index: 104)
Applied Psychophysiology and Biofeedback     Hybrid Journal   (Followers: 8, SJR: 0.677, h-index: 47)
Applied Research in Quality of Life     Hybrid Journal   (Followers: 10, SJR: 0.288, h-index: 15)
Applied Solar Energy     Hybrid Journal   (Followers: 17, SJR: 0.251, h-index: 6)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4, SJR: 0.351, h-index: 9)
Aquaculture Intl.     Hybrid Journal   (Followers: 22, SJR: 0.613, h-index: 40)
Aquarium Sciences and Conservation     Hybrid Journal   (Followers: 1)
Aquatic Ecology     Hybrid Journal   (Followers: 30, SJR: 0.646, h-index: 44)
Aquatic Geochemistry     Hybrid Journal   (Followers: 4, SJR: 0.764, h-index: 39)
Aquatic Sciences     Hybrid Journal   (Followers: 12, SJR: 1.172, h-index: 53)
Arabian J. for Science and Engineering     Hybrid Journal   (Followers: 5, SJR: 0.345, h-index: 20)
Arabian J. of Geosciences     Hybrid Journal   (Followers: 1, SJR: 0.417, h-index: 16)
Archaeological and Anthropological Sciences     Hybrid Journal   (Followers: 21, SJR: 1.056, h-index: 15)
Archaeologies     Hybrid Journal   (Followers: 12, SJR: 0.397, h-index: 13)
Archiv der Mathematik     Hybrid Journal   (Followers: 1, SJR: 0.597, h-index: 29)
Archival Science     Hybrid Journal   (Followers: 53, SJR: 0.804, h-index: 22)
Archive for History of Exact Sciences     Hybrid Journal   (Followers: 7, SJR: 0.28, h-index: 15)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 1, SJR: 0.946, h-index: 23)
Archive for Rational Mechanics and Analysis     Hybrid Journal   (SJR: 4.091, h-index: 66)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4, SJR: 0.865, h-index: 40)
Archives and Museum Informatics     Hybrid Journal   (Followers: 122)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4, SJR: 2.841, h-index: 40)
Archives of Dermatological Research     Hybrid Journal   (Followers: 6, SJR: 0.9, h-index: 65)
Archives of Environmental Contamination and Toxicology     Hybrid Journal   (Followers: 10, SJR: 0.846, h-index: 84)
Archives of Gynecology and Obstetrics     Hybrid Journal   (Followers: 17, SJR: 0.695, h-index: 47)
Archives of Microbiology     Hybrid Journal   (Followers: 8, SJR: 0.702, h-index: 85)
Archives of Orthopaedic and Trauma Surgery     Hybrid Journal   (Followers: 8, SJR: 1.039, h-index: 56)
Archives of Osteoporosis     Hybrid Journal   (Followers: 2, SJR: 1.092, h-index: 13)
Archives of Sexual Behavior     Hybrid Journal   (Followers: 9, SJR: 1.198, h-index: 74)
Archives of Toxicology     Hybrid Journal   (Followers: 17, SJR: 1.595, h-index: 76)
Archives of Virology     Hybrid Journal   (Followers: 5, SJR: 1.086, h-index: 90)
Archives of Women's Mental Health     Hybrid Journal   (Followers: 13, SJR: 1.264, h-index: 50)
Archivio di Ortopedia e Reumatologia     Hybrid Journal  
Archivum Immunologiae et Therapiae Experimentalis     Hybrid Journal   (Followers: 2, SJR: 1.2, h-index: 42)
ArgoSpine News & J.     Hybrid Journal   (SJR: 0.102, h-index: 3)
Argumentation     Hybrid Journal   (Followers: 5, SJR: 0.295, h-index: 18)
Arid Ecosystems     Hybrid Journal   (Followers: 3)
Arkiv för Matematik     Hybrid Journal   (Followers: 1, SJR: 0.948, h-index: 22)
Arnold Mathematical J.     Hybrid Journal   (Followers: 1)
Arthropod-Plant Interactions     Hybrid Journal   (Followers: 1, SJR: 0.797, h-index: 17)
Arthroskopie     Hybrid Journal   (Followers: 1, SJR: 0.145, h-index: 8)
Artificial Intelligence and Law     Hybrid Journal   (Followers: 10, SJR: 0.288, h-index: 25)
Artificial Intelligence Review     Hybrid Journal   (Followers: 14, SJR: 0.948, h-index: 48)
Artificial Life and Robotics     Hybrid Journal   (Followers: 8, SJR: 0.231, h-index: 14)
Asia Europe J.     Hybrid Journal   (Followers: 4, SJR: 0.247, h-index: 9)
Asia Pacific Education Review     Hybrid Journal   (Followers: 9, SJR: 0.371, h-index: 17)
Asia Pacific J. of Management     Hybrid Journal   (Followers: 12, SJR: 1.676, h-index: 50)
Asia-Pacific Education Researcher     Hybrid Journal   (Followers: 11, SJR: 0.353, h-index: 13)
Asia-Pacific Financial Markets     Hybrid Journal   (Followers: 2, SJR: 0.19, h-index: 15)
Asia-Pacific J. of Atmospheric Sciences     Hybrid Journal   (Followers: 20, SJR: 1.006, h-index: 14)
Asian Business & Management     Hybrid Journal   (Followers: 7, SJR: 0.41, h-index: 10)
Asian J. of Business Ethics     Hybrid Journal   (Followers: 7)
Asian J. of Criminology     Hybrid Journal   (Followers: 5, SJR: 0.263, h-index: 8)
AStA Advances in Statistical Analysis     Hybrid Journal   (Followers: 2, SJR: 0.681, h-index: 15)
AStA Wirtschafts- und Sozialstatistisches Archiv     Hybrid Journal   (Followers: 5, SJR: 0.195, h-index: 5)
ä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 Algorithmica
  [SJR: 0.898]   [H-I: 56]   [7 followers]  Follow
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
   ISSN (Print) 1432-0541 - ISSN (Online) 0178-4617
   Published by Springer-Verlag Homepage  [2353 journals]
  • Efficient Computation of Substring Equivalence Classes with Suffix Arrays
    • Authors: Kazuyuki Narisawa; Hideharu Hiratsuka; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
      Pages: 291 - 318
      Abstract: Abstract This paper considers enumeration of substring equivalence classes introduced by Blumer et al. (J ACM 34(3):578–595, 1987). These equivalence classes were originally proposed to define a text indexing structure called compact directed acyclic word graphs (CDAWGs). These equivalence classes are also useful for text analysis, since they group together redundant substrings with essentially identical occurrences. In this paper, we present how to enumerate these equivalence classes using only suffix arrays and two auxiliary arrays (rank arrays and lcp arrays), in O(n) time for a given string of length n over the integer alphabet. The proposed method overcomes all the existing algorithms which require \(O(n \log \sigma )\) time, where \(\sigma \) is the alphabet size. Our experimental results show that the proposed method is also practically faster and more memory efficient than the existing ones. Furthermore, we propose an O(n)-time algorithm which constructs the CDAWG of an input string over the integer alphabet. This algorithm is based on the above-mentioned algorithm to enumerate equivalence classes. Our experiments show that the proposed method runs faster than the existing algorithm on large alphabets.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0178-z
      Issue No: Vol. 79, No. 2 (2017)
  • General Caching Is Hard: Even with Small Pages
    • Authors: Lukáš Folwarczný; Jiří Sgall
      Pages: 319 - 339
      Abstract: Abstract Caching (also known as paging) is a classical problem concerning page replacement policies in two-level memory systems. General caching is the variant with pages of different sizes and fault costs. The strong NP-hardness of its two important cases, the fault model (each page has unit fault cost) and the bit model (each page has the same fault cost as size) has been established, but under the assumption that there are pages as large as half of the cache size. We prove that this already holds when page sizes are bounded by a small constant: The bit and fault models are strongly NP-complete even when page sizes are limited to \(\{1, 2, 3\}\) . Considering only the decision versions of the problems, general caching is equivalent to the unsplittable flow on a path problem and therefore our results also improve the hardness results about this problem.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0185-0
      Issue No: Vol. 79, No. 2 (2017)
  • Convex Hulls Under Uncertainty
    • Authors: Pankaj K. Agarwal; Sariel Har-Peled; Subhash Suri; Hakan Yıldız; Wuzhou Zhang
      Pages: 340 - 367
      Abstract: Abstract We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time–space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of \(\beta \) -hull that may be a useful representation of uncertain hulls.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0195-y
      Issue No: Vol. 79, No. 2 (2017)
  • Set It and Forget It: Approximating the Set Once Strip Cover Problem
    • Authors: Amotz Bar-Noy; Ben Baumer; Dror Rawitz
      Pages: 368 - 386
      Abstract: Abstract We consider the Set Once Strip Cover problem, in which n wireless sensors are deployed over a one-dimensional region. Each sensor has a fixed battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The problem is to find an assignment of radii and activation times that maximizes the length of time during which the entire region is covered. We show that this problem is NP-hard. In addition, we show that RoundRobin, the algorithm in which the sensors take turns covering the entire region, has a tight approximation guarantee of \(\frac{3}{2}\) . This result also applies to the more general Strip Cover problem, in which each radius may be set finitely-many times. Moreover, we show that the more general class of duty cycle algorithms, in which groups of sensors take turns covering the entire region, can do no better. Finally, we give an \(O(n^2 \log {n})\) -time optimization algorithm for the related Set Radius Strip Cover problem, in which sensors must be activated immediately.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0198-8
      Issue No: Vol. 79, No. 2 (2017)
  • Full-Fledged Real-Time Indexing for Constant Size Alphabets
    • Authors: Gregory Kucherov; Yakov Nekrich
      Pages: 387 - 400
      Abstract: Abstract In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in \(O( P +k)\) time, where P is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086–1095, 2008).
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0199-7
      Issue No: Vol. 79, No. 2 (2017)
  • On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
    • Authors: Michael A. Bekos; Sabine Cornelsen; Luca Grilli; Seok-Hee Hong; Michael Kaufmann
      Pages: 401 - 427
      Abstract: Abstract Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a linear-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-complete, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0200-5
      Issue No: Vol. 79, No. 2 (2017)
  • Efficiently Correcting Matrix Products
    • Authors: Leszek Gąsieniec; Christos Levcopoulos; Andrzej Lingas; Rasmus Pagh; Takeshi Tokuyama
      Pages: 428 - 443
      Abstract: Abstract We study the problem of efficiently correcting an erroneous product of two \(n\times n\) matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in \({\tilde{O}}(n^2+kn)\) time and a deterministic \({\tilde{O}}(kn^2)\) -time algorithm for this problem (where the notation \({\tilde{O}}\) suppresses polylogarithmic terms in n and k).
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0202-3
      Issue No: Vol. 79, No. 2 (2017)
  • The Book Thickness of 1-Planar Graphs is Constant
    • Authors: Michael A. Bekos; Till Bruckdorfer; Michael Kaufmann; Chrysanthi N. Raftopoulou
      Pages: 444 - 465
      Abstract: Abstract In a book embedding, the vertices of a graph are placed on the “spine” of a book and the edges are assigned to “pages”, so that edges on the same page do not cross. In this paper, we prove that every 1-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is \(O(\sqrt{n})\) , where n is the number of vertices of the graph.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0203-2
      Issue No: Vol. 79, No. 2 (2017)
  • Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs
    • Authors: Surender Baswana; Shahbaz Khan
      Pages: 466 - 483
      Abstract: Abstract Depth First Search (DFS) tree is a fundamental data structure for graphs used in solving various algorithmic problems. However, very few results are known for maintaining DFS tree in a dynamic environment—insertion or deletion of edges. We present the first algorithm for maintaining a DFS tree for an undirected graph under insertion of edges. For processing any arbitrary online sequence of edge insertions, this algorithm takes total \(O(n^2)\) time.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0204-1
      Issue No: Vol. 79, No. 2 (2017)
  • Efficient Sampling Methods for Discrete Distributions
    • Authors: Karl Bringmann; Konstantinos Panagiotou
      Pages: 484 - 508
      Abstract: Abstract We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities \(p_1, \dots , p_n\) . First, we consider the problem of sampling from the distribution where the i-th event has probability proportional to \(p_i\) . Second, we study the problem of sampling a subset which includes the i-th event independently with probability \(p_i\) . For both problems we present on two different classes of inputs—sorted and general probabilities—efficient data structures consisting of a preprocessing and a query algorithm. Varying the allotted preprocessing time yields a trade-off between preprocessing and query time, which we prove to be asymptotically optimal everywhere.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0205-0
      Issue No: Vol. 79, No. 2 (2017)
  • Optimal Parallel Quantum Query Algorithms
    • Authors: Stacey Jeffery; Frederic Magniez; Ronald de Wolf
      Pages: 509 - 529
      Abstract: Abstract We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically \(\Theta ((n/p)^{2/3})\) p-parallel queries for element distinctness and \(\Theta ((n/p)^{k/(k+1)})\) for \(k\) -sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel query complexity are polynomially related for all total functions f when p is small compared to f’s block sensitivity.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0206-z
      Issue No: Vol. 79, No. 2 (2017)
  • Building Efficient and Compact Data Structures for Simplicial Complexes
    • Authors: Jean-Daniel Boissonnat; Karthik C. S.; Sébastien Tavenas
      Pages: 530 - 567
      Abstract: The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0207-y
      Issue No: Vol. 79, No. 2 (2017)
  • Efficient Computation of Optimal Energy and Fractional Weighted Flow
           Trade-Off Schedules
    • Authors: Antonios Antoniadis; Neal Barcelo; Mario Consuegra; Peter Kling; Michael Nugent; Kirk Pruhs; Michele Scquizzato
      Pages: 568 - 597
      Abstract: Abstract We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal–dual formulation of the problem.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0208-x
      Issue No: Vol. 79, No. 2 (2017)
  • On the Value of Job Migration in Online Makespan Minimization
    • Authors: Susanne Albers; Matthias Hellwig
      Pages: 598 - 623
      Abstract: Abstract Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of n jobs has to be scheduled non-preemptively on m machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range [1.88, 1.9201]. Currently no randomized online algorithm with a smaller competitiveness is known, for general m. In this paper we explore the power of job migration, i.e. an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is \(\alpha _m\) -competitive, for any \(m\ge 2\) , where \(\alpha _m\) is the solution of a certain equation. For \(m=2\) , \(\alpha _2 = 4/3\) and \(\lim _{m\rightarrow \infty } \alpha _m = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2)) \approx 1.4659\) . Here \(W_{-1}\) is the lower branch of the Lambert W function. For \(m\ge 11\) , the algorithm uses at most 7m migration operations. For smaller m, 8m to 10m operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses o(n) job migrations can achieve a competitive ratio smaller than \(\alpha _m\) . We finally trade performance for migrations. We give a family of algorithms that is c-competitive, for any \(5/3\le c \le 2\) . For \(c= 5/3\) , the strategy uses at most 4m job migrations. For \(c=1.75\) , at most 2.5m migrations are used.
      PubDate: 2017-10-01
      DOI: 10.1007/s00453-016-0209-9
      Issue No: Vol. 79, No. 2 (2017)
  • Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal
    • Authors: Bart M. P. Jansen; Astrid Pieterse
      Pages: 3 - 28
      Abstract: Abstract We present several sparsification lower and upper bounds for classic problems in graph theory and logic. For the problems 4-Coloring, (Directed) Hamiltonian Cycle, and (Connected) Dominating Set, we prove that there is no polynomial-time algorithm that reduces any n-vertex input to an equivalent instance, of an arbitrary problem, with bitsize  \(O(n^{2-\varepsilon })\) for  \(\varepsilon > 0\) , unless \(\mathsf {NP \subseteq coNP/poly}\) and the polynomial-time hierarchy collapses. These results imply that existing linear-vertex kernels for k-Nonblocker and k-Max Leaf Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be improved to have \(O(k^{2-\varepsilon })\) edges, unless \(\mathsf {NP \subseteq coNP/poly}\) . We also present a positive result and exhibit a non-trivial sparsification algorithm for d-Not-All-Equal-SAT. We give an algorithm that reduces an n-variable input with clauses of size at most d to an equivalent input with  \(O(n^{d-1})\) clauses, for any fixed d. Our algorithm is based on a linear-algebraic proof of Lovász that bounds the number of hyperedges in critically 3-chromatic d-uniform n-vertex hypergraphs by  \(\left( {\begin{array}{c}n\\ d-1\end{array}}\right) \) . We show that our kernel is tight under the assumption that \(\mathsf {NP} \nsubseteq \mathsf {coNP}/\mathsf {poly}\) .
      PubDate: 2017-09-01
      DOI: 10.1007/s00453-016-0189-9
      Issue No: Vol. 79, No. 1 (2017)
  • On Kernelization and Approximation for the Vector Connectivity Problem
    • Authors: Stefan Kratsch; Manuel Sorge
      Pages: 96 - 138
      Abstract: In the Vector Connectivity problem we are given an undirected graph \(G=(V,E)\) , a demand function \(\lambda :V\rightarrow \{0,\ldots ,d\}\) , and an integer k. The question is whether there exists a set S of at most k vertices such that every vertex \(v\in V{\setminus } S\) has at least \(\lambda (v)\) vertex-disjoint paths to S; this abstractly captures questions about placing servers or warehouses relative to demands. The problem is \(\mathsf {NP}\) -hard already for instances with \(d=4\) (Cicalese et al., Theoretical Computer Science ’15), admits a log-factor approximation (Boros et al., Networks ’14), and is fixed-parameter tractable in terms of k (Lokshtanov, unpublished ’14). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector d-Connectivity where the upper bound d on demands is a fixed constant. For Vector d-Connectivity we give a factor d-approximation algorithm and construct a vertex-linear kernelization, that is, an efficient reduction to an equivalent instance with \(f(d)k=O(k)\) vertices. For Vector Connectivity we have a factor \(\mathsf {opt} \) -approximation and we can show that it has no kernelization to size polynomial in k or even \(k+d\) unless \(\mathsf {NP} \subseteq \mathsf {coNP}/\mathsf {poly}\) , which shows that \(f(d){\text {poly}}(k)\) is optimal for Vector d-Connectivity. Finally, we give a simple randomized fixed-parameter algorithm for Vector Connectivity with respect to k based on matroid intersection.
      PubDate: 2017-09-01
      DOI: 10.1007/s00453-016-0231-y
      Issue No: Vol. 79, No. 1 (2017)
  • Linear Kernels for Outbranching Problems in Sparse Digraphs
    • Authors: Marthe Bonamy; Łukasz Kowalik; Michał Pilipczuk; Arkadiusz Socała
      Pages: 159 - 188
      Abstract: Abstract In the \(k\) -Leaf Out-Branching and \(k\) -Internal Out-Branching problems we are given a directed graph D with a designated root r and a nonnegative integer k. The question is whether there exists an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems have been studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with \(O(k^2)\) vertices are known on general graphs. In this work we show that \(k\) -Leaf Out-Branching admits a kernel with O(k) vertices on \({{\mathcal {H}}}\) -minor-free graphs, for any fixed family of graphs \({{\mathcal {H}}}\) , whereas \(k\) -Internal Out-Branching admits a kernel with O(k) vertices on any graph class of bounded expansion.
      PubDate: 2017-09-01
      DOI: 10.1007/s00453-016-0244-6
      Issue No: Vol. 79, No. 1 (2017)
  • Extending the Kernel for Planar Steiner Tree to the Number of Steiner
    • Authors: Ondřej Suchý
      Pages: 189 - 210
      Abstract: Abstract In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by \( T +k\) , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals  T is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs.
      PubDate: 2017-09-01
      DOI: 10.1007/s00453-016-0249-1
      Issue No: Vol. 79, No. 1 (2017)
  • Complexity and Approximability of Parameterized MAX-CSPs
    • Authors: Holger Dell; Eun Jung Kim; Michael Lampis; Valia Mitsou; Tobias Mömke
      Pages: 230 - 250
      Abstract: Abstract We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable–constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types \({\text {AND}}\) , \({\text {OR}}\) , \({\text {PARITY}}\) , and \({\text {MAJORITY}}\) , and with various parameters k, and we attempt to fully classify them into the following three cases: The exact optimum can be computed in \(\textsf {FPT}\) time. It is -hard to compute the exact optimum, but there is a randomized \(\textsf {FPT}\) approximation scheme ( \(\textsf {FPT\text {-}AS}\) ), which computes a \((1{-}\epsilon )\) -approximation in time \(f(k,\epsilon ) \cdot {\text {poly}}(n)\) . There is no \(\textsf {FPT\text {-}AS}\) unless . For the corresponding standard CSPs, we establish \(\textsf {FPT}\) versus -hardness results.
      PubDate: 2017-09-01
      DOI: 10.1007/s00453-017-0310-8
      Issue No: Vol. 79, No. 1 (2017)
  • Guest Editorial: Special Issue on Parameterized and Exact Computation
    • Authors: Thore Husfeldt; Iyad Kanj
      PubDate: 2017-06-27
      DOI: 10.1007/s00453-017-0339-8
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-2016