for Journals by Title or ISSN
for Articles by Keywords

Publisher: Springer-Verlag   (Total: 2345 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 2345 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: 10, 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: 3)
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: 3, 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)
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: 2)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 53, 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: 23, 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: 40, 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: 14, 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: 19, 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: 6, 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: 14, SJR: 1.094, h-index: 87)
American J. of Cardiovascular Drugs     Hybrid Journal   (Followers: 10, SJR: 0.864, h-index: 39)
American J. of Community Psychology     Hybrid Journal   (Followers: 24, SJR: 1.237, h-index: 83)
American J. of Criminal Justice     Hybrid Journal   (Followers: 7, 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: 7, 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: 4, SJR: 0.665, h-index: 7)
Analysis in Theory and Applications     Hybrid Journal  
Analysis of Verbal Behavior     Hybrid Journal   (Followers: 4)
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: 12, 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: 8)
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: 9, 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: 9)
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: 11, 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 Categorical Structures     Hybrid Journal   (Followers: 2, SJR: 0.361, h-index: 21)
Applied Composite Materials     Hybrid Journal   (Followers: 47, 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: 7, SJR: 0.541, h-index: 13)
Applied Intelligence     Hybrid Journal   (Followers: 12, SJR: 0.777, h-index: 43)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 3, 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: 61, 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: 7, 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: 3, 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: 52, 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: 120)
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: 16, 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: 9, 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: 7, 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  
Astronomy and Astrophysics Review     Hybrid Journal   (Followers: 21, SJR: 4.511, h-index: 44)
Astronomy Letters     Hybrid Journal   (Followers: 20, SJR: 0.58, h-index: 30)

        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  [2345 journals]
  • Top- k Term-Proximity in Succinct Space
    • Authors: J. Ian Munro; Gonzalo Navarro; Jesper Sindahl Nielsen; Rahul Shah; Sharma V. Thankachan
      Pages: 379 - 393
      Abstract: Let \(\mathcal {D} = \{\mathsf {T}_1,\mathsf {T}_2, \ldots ,\mathsf {T}_D\}\) be a collection of D string documents of n characters in total, that are drawn from an alphabet set \(\varSigma =[\sigma ]\) . The top-k document retrieval problem is to preprocess \(\mathcal{D}\) into a data structure that, given a query \((P[1\ldots p],k)\) , can return the k documents of \(\mathcal{D}\) most relevant to the pattern P. The relevance is captured using a predefined ranking function, which depends on the set of occurrences of P in \(\mathsf {T}_d\) . For example, it can be the term frequency (i.e., the number of occurrences of P in \(\mathsf {T}_d\) ), or it can be the term proximity (i.e., the distance between the closest pair of occurrences of P in \(\mathsf {T}_d\) ), or a pattern-independent importance score of \(\mathsf {T}_d\) such as PageRank. Linear space and optimal query time solutions already exist for the general top-k document retrieval problem. Compressed and compact space solutions are also known, but only for a few ranking functions such as term frequency and importance. However, space efficient data structures for term proximity based retrieval have been evasive. In this paper we present the first sub-linear space data structure for this relevance function, which uses only o(n) bits on top of any compressed suffix array of \(\mathcal{D}\) and solves queries in \(O((p+k) {{\mathrm{polylog}}}\,\,n)\) time. We also show that scores that consist of a weighted combination of term proximity, term frequency, and document importance, can be handled using twice the space required to represent the text collection.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0167-2
      Issue No: Vol. 78, No. 2 (2017)
  • An External-Memory Algorithm for String Graph Construction
    • Authors: Paola Bonizzoni; Gianluca Della Vedova; Yuri Pirola; Marco Previtali; Raffaella Rizzi
      Pages: 394 - 424
      Abstract: Some recent results (Bauer et al. in Algorithms in bioinformatics, Springer, Berlin, pp 326–337, 2012; Cox et al. in Algorithms in bioinformatics, Springer, Berlin, pp. 214–224, 2012; Rosone and Sciortino in The nature of computation. Logic, algorithms, applications, Springer, Berlin, pp 353–364, 2013) have introduced external-memory algorithms to compute self-indexes of a set of strings, mainly via computing the Burrows–Wheeler transform of the input strings. The motivations for those results stem from Bioinformatics, where a large number of short strings (called reads) are routinely produced and analyzed. In that field, a fundamental problem is to assemble a genome from a large set of much shorter samples extracted from the unknown genome. The approaches that are currently used to tackle this problem are memory-intensive. This fact does not bode well with the ongoing increase in the availability of genomic data. A data structure that is used in genome assembly is the string graph, where vertices correspond to samples and arcs represent two overlapping samples. In this paper we address an open problem of Simpson and Durbin (Bioinformatics 26(12):i367–i373, 2010): to design an external-memory algorithm to compute the string graph.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0165-4
      Issue No: Vol. 78, No. 2 (2017)
  • Strategyproof Mechanisms for Competitive Influence in Networks
    • Authors: Allan Borodin; Mark Braverman; Brendan Lucier; Joel Oren
      Pages: 425 - 452
      Abstract: Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology. We study this model from the perspective of a central mechanism, such as a social networking platform, that can optimize seed placement as a service for the advertisers. We ask: given the reported budgets of the competing firms, how should a mechanism choose seeds to maximize overall efficiency? Beyond the algorithmic problem, competition raises issues of strategic behaviour: rational agents should be incentivized to truthfully report their advertising budget. For a general class of influence spread models, we show that when there are two players, the social welfare can be \(\frac{e}{e-1}\) -approximated by a polynomial-time strategyproof mechanism. Our mechanism uses a dynamic programming procedure to randomize the order in which advertisers are allocated seeds according to a greedy method. For three or more players, we demonstrate that under an additional assumption (satisfied by many existing models of influence spread) there exists a simpler strategyproof \(\frac{e}{e-1}\) -approximation mechanism; notably, this natural greedy mechanism is not necessarily strategyproof when there are only two players.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0169-0
      Issue No: Vol. 78, No. 2 (2017)
  • Max-min Fair Rate Allocation and Routing in Energy Harvesting Networks:
           Algorithmic Analysis
    • Authors: Jelena Marašević; Clifford Stein; Gil Zussman
      Pages: 521 - 557
      Abstract: This paper considers max-min fair rate allocation and routing in energy harvesting networks where fairness is required among both the nodes and the time slots. Unlike most previous work on fairness, we focus on multihop topologies and consider different routing methods. We assume a predictable energy profile and focus on the design of efficient and optimal algorithms that can serve as benchmarks for distributed and approximate algorithms. We first develop an algorithm that obtains a max-min fair rate assignment for any routing that is specified at the input. We then turn to the problem of determining a “good” routing. For time-invariable unsplittable routing, we develop an algorithm that finds routes that maximize the minimum rate assigned to any node in any slot. For fractional routing, we derive a combinatorial algorithm for the time-invariable case with constant rates. We show that the time-variable case is at least as hard as the 2-commodity feasible flow problem and design an FPTAS to combat the high running time. Finally, we show that finding an unsplittable routing or a routing tree that provides lexicographically maximum rate assignment (i.e., the best in the max-min fairness terms) is NP-hard, even for a time horizon of a single slot. Our analysis provides insights into the problem structure and can be applied to other related fairness problems.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0171-6
      Issue No: Vol. 78, No. 2 (2017)
  • Preface to the Special Issue on Theory of Genetic and Evolutionary
    • Authors: Carola Doerr; Francisco Chicano
      Pages: 558 - 560
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-017-0280-x
      Issue No: Vol. 78, No. 2 (2017)
  • Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable
           k -CNF Formulas
    • Authors: Benjamin Doerr; Frank Neumann; Andrew M. Sutton
      Pages: 561 - 586
      Abstract: We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple ( \(1+1\) ) evolutionary algorithm with high probability finds a satisfying assignment in time \(O(n \log n)\) when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below \(\frac{1}{k(k-1)}\) . We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the ( \(1+1\) ) EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942–951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0190-3
      Issue No: Vol. 78, No. 2 (2017)
  • Towards a Runtime Comparison of Natural and Artificial Evolution
    • Authors: Tiago Paixão; Jorge Pérez Heredia; Dirk Sudholt; Barbora Trubenová
      Pages: 681 - 713
      Abstract: Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0212-1
      Issue No: Vol. 78, No. 2 (2017)
  • On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation
    • Authors: Dogan Corus; Jun He; Thomas Jansen; Pietro S. Oliveto; Dirk Sudholt; Christine Zarges
      Pages: 714 - 740
      Abstract: Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1) EA using standard bit mutation (SBM) it is well known that OneMax is an easiest function with unique optimum while Trap is a hardest. In this paper we extend the analysis of easiest function classes to the contiguous somatic hypermutation (CHM) operator used in artificial immune systems. We define a function MinBlocks and prove that it is an easiest function for the (1+1) EA using CHM, presenting both a runtime and a fixed budget analysis. Since MinBlocks is, up to a factor of 2, a hardest function for standard bit mutations, we consider the effects of combining both operators into a hybrid algorithm. We rigorously prove that by combining the advantages of k operators, several hybrid algorithmic schemes have optimal asymptotic performance on the easiest functions for each individual operator. In particular, the hybrid algorithms using CHM and SBM have optimal asymptotic performance on both OneMax and MinBlocks. We then investigate easiest functions for hybrid schemes and show that an easiest function for a hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator.
      PubDate: 2017-06-01
      DOI: 10.1007/s00453-016-0201-4
      Issue No: Vol. 78, No. 2 (2017)
  • Guest Editorial: Special Issue on Parameterized and Exact Computation
    • PubDate: 2017-06-27
  • A Clustering-Based Approach to Kinetic Closest Pair
    • Abstract: Given a set P of n moving points in fixed dimension d, where the trajectory of each point is a polynomial of degree bounded by some constant, we present a kinetic data structure (KDS) for maintenance of the closest pair on P. Assuming the closest pair distance is between 1 and \(\varDelta \) over time, our KDS uses \(O(n \log \varDelta )\) space and processes \(O(n^{2} \beta \log \varDelta \log n + n^{2} \beta \log \varDelta \log \log \varDelta )\) events, each in worst-case time \(O(\log ^2 n + \log ^2 \log \varDelta )\) . Here, \(\beta \) is an extremely slow-growing function. The locality of the KDS is \(O(\log n + \log \log \varDelta )\) . Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time \(O(\log \varDelta \log ^2 n + \log \varDelta \log ^2 \log \varDelta )\) . Also, we use a similar approach to provide a KDS for the all \(\varepsilon \) -nearest neighbors in \(\mathbb {R}^d\) . The complexities of the previous KDSs, for both closest pair and all \(\varepsilon \) -nearest neighbors, have polylogarithmic factors, where the number of logs depends on dimension d. Assuming \(\varDelta \) is polynomial in n, our KDSs obtain improvements on the previous KDSs. Our solutions are based on a kinetic clustering on P. Though we use ideas from the previous clustering KDS by Hershberger, we simplify and improve his work.
      PubDate: 2017-06-21
  • A Moderately Exponential Time Algorithm for k -IBDD Satisfiability
    • Abstract: We present a satisfiability algorithm for k-indexed binary decision diagrams (k-IBDDs). The proposed exponential space and deterministic algorithm solves the satisfiability of k-IBDDs, i.e., k-IBDD SAT, for instances with n variables and cn nodes in \(O\left( 2^{(1-\mu _k(c))n}\right) \) time, where \(\mu _k(c) = \varOmega \left( \frac{1}{(k^2 2^k\log {c})^{2^{k-1}-1}}\right) \) . We also provide a polynomial space and deterministic algorithm that solves a k-IBDD SAT of polynomial size for any constant \(k \ge 2\) in \(O\left( 2^{ n - n^{ 1/2^{k-1} }}\right) \) time. In addition, the proposed algorithm is applicable to equivalence checking of two IBDDs.
      PubDate: 2017-06-20
  • Minimizing Latency of Capacitated k -Tours
    • Abstract: We study variants of the capacitated vehicle routing problem. In the multiple depot capacitated k-travelling repairmen problem (MD-CkTRP), we have a collection of clients to be served by one vehicle in a fleet of k identical vehicles based at given depots. Each client has a given demand that must be satisfied, and each vehicle can carry a total of at most Q demand before it must resupply at its original depot. We wish to route the vehicles in a way that obeys the constraints while minimizing the average time (latency) required to serve a client. This generalizes the Multi-depot k-Travelling Repairman Problem (MD-kTRP) (Chaudhuri et al. in 44th IEEE-FOCS, pp 36–45, 2003; Post and Swamy in 26th ACM-SIAM SODA, pp 512–531, 2015) to the capacitated vehicle setting, and while it has been previously studied (Lysgaard and Wholk in Eur J Oper Res 236(3):800–810, 2014), no approximation algorithm with a proven ratio is known. We give a 42.49-approximation to this general problem, and refine this constant to 25.49 when clients have unit demands. As far as we are aware, these are the first constant-factor approximations for capacitated vehicle routing problems with a latency objective. We achieve these results by developing a framework allowing us to solve a wider range of latency problems, and crafting various orienteering-style oracles for use in this framework. We also show a simple LP rounding algorithm has a better approximation ratio for the maximum coverage problem with groups (MCG), first studied by Chekuri and Kumar (Approximation, randomization, and combinatorial optimization, algorithms and techniques, pp 72–83, 2004), and use it as a subroutine in our framework. Our approximation ratio for MD-CkTRP when restricted to uncapacitated setting matches the best known bound for it (Post and Swamy in 26th ACM-SIAM SODA, pp 512–531, 2015). With our framework, any improvements to our oracles or our MCG approximation will result in improved approximations to the corresponding k-TRP problem.
      PubDate: 2017-06-20
  • Faster Information Gathering in Ad-Hoc Radio Tree Networks
    • Authors: Marek Chrobak; Kevin P. Costello
      Abstract: We study information gathering in ad-hoc radio networks. Initially, each node of the network has a piece of information called a rumor, and the overall objective is to gather all these rumors in the designated target node. The ad-hoc property refers to the fact that the topology of the network is unknown when the computation starts. Aggregation of rumors is not allowed, which means that each node may transmit at most one rumor in one step. We focus on networks with tree topologies, that is we assume that the network is a tree with all edges directed towards the root, but, being ad-hoc, its actual topology is not known. We provide two deterministic algorithms for this problem. For the model that does not assume any collision detection nor acknowledgement mechanisms, we give an \(O(n\log \log n)\) -time algorithm, improving the previous upper bound of \(O(n\log n)\) . We then show that this running time can be reduced to O(n), which is asymptotically optimal, if the model allows for acknowledgements of successful transmissions.
      PubDate: 2017-06-20
      DOI: 10.1007/s00453-017-0336-y
  • Shortest $$(A+B)$$ ( A + B ) -Path Packing Via Hafnian
    • Authors: Hiroshi Hirai; Hiroyuki Namba
      Abstract: Björklund and Husfeldt developed a randomized polynomial time algorithm to solve the shortest two disjoint paths problem. Their algorithm is based on computation of permanents modulo 4 and the isolation lemma. In this paper, we consider the following generalization of the shortest two disjoint paths problem, and develop a similar algebraic algorithm. The shortest perfect \((A+B)\) -path packing problem is: given an undirected graph G and two disjoint node subsets A, B with even cardinalities, find shortest \( A /2+ B /2\) disjoint paths whose ends are both in A or both in B. Besides its NP-hardness, we prove that this problem can be solved in randomized polynomial time if \( A + B \) is fixed. Our algorithm basically follows the framework of Björklund and Husfeldt but uses a new technique: computation of hafnian modulo \(2^k\) combined with Gallai’s reduction from T-paths to matchings. We also generalize our technique for solving other path packing problems, and discuss its limitation.
      PubDate: 2017-06-14
      DOI: 10.1007/s00453-017-0334-0
  • Sampling in Space Restricted Settings
    • Authors: Anup Bhattacharya; Davis Issac; Ragesh Jaiswal; Amit Kumar
      Abstract: Space efficient algorithms play an important role in dealing with large amount of data. In such settings, one would like to analyze the large data using small amount of “working space”. One of the key steps in many algorithms for analyzing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings—(i) the streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) the query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in the above two settings: In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using \(O(\log n)\) random bits and \(O(\log n)\) bits of space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. In the query model, there are n elements with weights \(w_1, \ldots , w_n\) (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using \(nw +1 \) bits of space (whereas, the information theoretic lower bound is nw). We consider the approximate sampling problem, where we are given an error parameter \(\varepsilon \) , and the sampling probability of an element can be off by an \(\varepsilon \) factor. We give matching upper and lower bounds for this problem.
      PubDate: 2017-06-14
      DOI: 10.1007/s00453-017-0335-z
  • Fast Compatibility Testing for Rooted Phylogenetic Trees
    • Authors: Yun Deng; David Fernández-Baca
      Abstract: We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let \(\mathcal {P}= \{T_1, \ldots , T_k\}\) be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a phylogenetic tree T with the following property: for each \(i \in \{1, \dots , k\}\) , \(T_i\) can be obtained from the restriction of T to the species set of \(T_i\) by contracting zero or more edges. If such a tree T exists, we say that \(\mathcal {P}\) is compatible and that T displays \(\mathcal {P}\) . Our approach leads to a \(O(M_\mathcal {P}\log ^2 M_\mathcal {P})\) algorithm for the tree compatibility problem, where \(M_\mathcal {P}\) is the total number of nodes and edges in \(\mathcal {P}\) . Our algorithm either returns a tree that displays \(\mathcal {P}\) or reports that \(\mathcal {P}\) is incompatible. Unlike previous algorithms, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, our algorithm is equally fast on highly resolved and highly unresolved trees.
      PubDate: 2017-06-06
      DOI: 10.1007/s00453-017-0330-4
  • Partial-Matching RMS Distance Under Translation: Combinatorics and
    • Authors: Rinat Ben-Avraham; Matthias Henze; Rafel Jaume; Balázs Keszegh; Orit E. Raz; Micha Sharir; Igor Tubis
      Abstract: We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets A and B, in the plane, with \(m= B \ll n= A \) , in the partial-matching setup, in which each point in B is matched to a distinct point in A. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision \({\mathcal {D}}_{B,A}\) of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is \(O(n^2m^{3.5} (e \ln m+e)^m)\) , so it is only quadratic in A . These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time.
      PubDate: 2017-06-06
      DOI: 10.1007/s00453-017-0326-0
  • Complexity Results for Generating Subgraphs
    • Authors: Vadim E. Levit; David Tankus
      Abstract: A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w -well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition \(B_{X}\) and \(B_{Y}\) . Then B is generating if there exists an independent set S such that \(S \cup B_{X}\) and \(S \cup B_{Y}\) are both maximal independent sets of G. In the restricted case that a generating subgraph B is isomorphic to \(K_{1,1}\) , the unique edge in B is called a relating edge. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. In this article we discuss the connections among these problems, provide proofs for NP-completeness for several restricted cases, and present polynomial characterizations for some other cases.
      PubDate: 2017-06-02
      DOI: 10.1007/s00453-017-0325-1
  • On the Planar Split Thickness of Graphs
    • Authors: David Eppstein; Philipp Kindermann; Stephen Kobourov; Giuseppe Liotta; Anna Lubiw; Aude Maignan; Debajyoti Mondal; Hamideh Vosoughpour; Sue Whitesides; Stephen Wismath
      Abstract: Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittability in linear time, for a constant k.
      PubDate: 2017-06-02
      DOI: 10.1007/s00453-017-0328-y
  • Model-Based Segmentation and Classification of Trajectories
    • Authors: Sander P. A. Alewijnse; Kevin Buchin; Maike Buchin; Stef Sijben; Michel A. Westenberg
      Abstract: We present efficient algorithms for segmenting and classifying trajectories based on a movement model parameterised by a single parameter, like the Brownian bridge movement model. Segmentation is the problem of subdividing a trajectory into interior-disjoint parts such that each part is homogeneous in its movement characteristics. We formalise this using the likelihood of the model parameter, and propose a new algorithm for trajectory segmentation based on this. We consider the case where a discrete set of m parameter values is given and present an algorithm to compute an optimal segmentation with respect to an information criterion in O(nm) time for a trajectory with n sampling points. We also present an algorithm that efficiently computes the optimal segmentation if we allow the parameter values to be drawn from a continuous domain. Classification is the problem of assigning trajectories to classes of similar movement characteristics. The set of trajectories might for instance be the subtrajectories resulting from segmenting a trajectory, thus identifying movement phases. We give an algorithm to compute the optimal classification with respect to an information criterion in \(O(m^2 + km\log m)\) time for m parameter values and k trajectories, assuming bitonic likelihood functions. We also show that classification is NP-hard if the parameter values are allowed to vary continuously and present an algorithm that solves the problem in polynomial time under mild assumptions on the input.
      PubDate: 2017-06-02
      DOI: 10.1007/s00453-017-0329-x
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