for Journals by Title or ISSN
for Articles by Keywords
help

Publisher: Springer-Verlag   (Total: 2335 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 2335 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: 16, SJR: 1.192, h-index: 74)
AAPS PharmSciTech     Hybrid Journal   (Followers: 6, SJR: 0.718, h-index: 54)
Abdominal Imaging     Hybrid Journal   (Followers: 16, 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: 25, SJR: 0.378, h-index: 30)
Acoustical Physics     Hybrid Journal   (Followers: 10, SJR: 0.355, h-index: 20)
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: 6, SJR: 1.818, h-index: 22)
Acta Informatica     Hybrid Journal   (Followers: 5, SJR: 0.524, h-index: 32)
Acta Mathematica     Hybrid Journal   (Followers: 9, 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: 18, SJR: 0.898, h-index: 52)
Acta Mechanica Sinica     Hybrid Journal   (Followers: 4, 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: 7, 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: 48, SJR: 1.113, h-index: 14)
Advances in Gerontology     Partially Free   (Followers: 7, 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: 6, 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: 8, 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: 6, 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: 2, SJR: 0.706, h-index: 19)
Akupunktur & Aurikulomedizin     Full-text available via subscription   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 2, SJR: 0.566, h-index: 18)
Algebra Universalis     Hybrid Journal   (Followers: 2, SJR: 0.388, h-index: 22)
Algebras and Representation Theory     Hybrid Journal   (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: 3, 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: 5, 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: 20, SJR: 0.293, h-index: 13)
American Sociologist     Hybrid Journal   (Followers: 10, 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: 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: 32, 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: 13, 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: 10, 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: 26, 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: 13, 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 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: 9, 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: 7, 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: 45, 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: 45, 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: 13, 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: 8, SJR: 0.535, h-index: 121)
Applied Physics B: Lasers and Optics     Hybrid Journal   (Followers: 22, SJR: 0.983, h-index: 104)
Applied Psychophysiology and Biofeedback     Hybrid Journal   (Followers: 5, 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: 16, 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: 21, SJR: 0.613, h-index: 40)
Aquarium Sciences and Conservation     Hybrid Journal   (Followers: 1)
Aquatic Ecology     Hybrid Journal   (Followers: 31, 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   (SJR: 0.597, h-index: 29)
Archival Science     Hybrid Journal   (Followers: 51, 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 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: 16, 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: 4, 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: 4, SJR: 0.295, h-index: 18)
Arid Ecosystems     Hybrid Journal   (Followers: 3)
Arkiv för Matematik     Hybrid Journal   (SJR: 0.948, h-index: 22)
Arnold Mathematical J.     Hybrid Journal   (Followers: 1)
Arthropod-Plant Interactions     Hybrid Journal   (Followers: 2, SJR: 0.797, h-index: 17)
Arthroskopie     Hybrid Journal   (Followers: 1, SJR: 0.145, h-index: 8)
Artificial Intelligence and Law     Hybrid Journal   (Followers: 8, SJR: 0.288, h-index: 25)
Artificial Intelligence Review     Hybrid Journal   (Followers: 15, 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: 11, 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: 19, SJR: 0.58, h-index: 30)
Astronomy Reports     Hybrid Journal   (Followers: 12, SJR: 0.473, h-index: 23)
Astrophysical Bulletin     Hybrid Journal   (Followers: 2, SJR: 0.469, h-index: 11)
Astrophysics     Hybrid Journal   (Followers: 22, SJR: 0.243, h-index: 11)

        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  [2335 journals]
  • Binary Pattern Tile Set Synthesis Is NP-Hard
    • Authors: Lila Kari; Steffen Kopecki; Pierre-Étienne Meunier; Matthew J. Patitz; Shinnosuke Seki
      Pages: 1 - 46
      Abstract: We solve an open problem, stated in 2008, about the feasibility of designing efficient algorithmic self-assembling systems which produce 2-dimensional colored patterns. More precisely, we show that the problem of finding the smallest tile assembly system which rectilinearly self-assembles an input pattern with 2 colors (i.e., 2-Pats) is \(\mathbf {NP}\) -hard. Of both theoretical and practical significance, the more general k-Pats problem has been studied in a series of papers which have shown k-Pats to be \(\mathbf {NP}\) -hard for \(k=60\) , \(k=29\) , and then \(k=11\) . In this paper, we prove the fundamental conjecture that 2-Pats is \(\mathbf {NP}\) -hard, concluding this line of study. While most of our proof relies on standard mathematical proof techniques, one crucial lemma makes use of a computer-assisted proof, which is a relatively novel but increasingly utilized paradigm for deriving proofs for complex mathematical problems. This tool is especially powerful for attacking combinatorial problems, as exemplified by the proof for the four color theorem and the recent important advance on the Erdős discrepancy problem using computer programs. In this paper, these techniques will be brought to a new order of magnitude, computational tasks corresponding to one CPU-year. We massively parallelize our program, and provide a full proof of its correctness. Its source code is freely available online.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0154-7
      Issue No: Vol. 78, No. 1 (2017)
       
  • Minimizing the Aggregate Movements for Interval Coverage
    • Authors: Aaron M. Andrews; Haitao Wang
      Pages: 47 - 85
      Abstract: We consider an interval coverage problem. Given n intervals of the same length on a line L and a line segment B on L, we want to move the intervals along L such that every point of B is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in \(O(n^2)\) time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an \(O(n\log n)\) time algorithm. We also show an \(\varOmega (n\log n)\) time lower bound for this problem, which implies the optimality of our algorithm.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0153-8
      Issue No: Vol. 78, No. 1 (2017)
       
  • Steiner Trees with Bounded RC-Delay
    • Authors: Rudolf Scheifele
      Pages: 86 - 109
      Abstract: We consider the Minimum Elmore Delay Steiner Tree Problem, which is a key problem in VLSI design: We are given a set of pins which have to be connected by a Steiner tree. One of the pins is the source. Challenging timing constraints impose tight bounds on the delay of propagating a signal from the source to the other pins. The commonly used measure is Elmore delay (Elmore in J Appl Phys 19:55–63, 1948). We consider two variants: minimizing the maximum Elmore delay or a weighted sum of Elmore delays. Both variants are strongly NP-hard even for very restricted special cases. Although it is a central problem in VLSI design (Kahng and Robins in On optimal interconnections for VLSI. Kluwer, Boston, 1995; Korte and Vygen in Building bridges—between mathematics and computer science. Springer, Berlin, pp 333–368, 2008), no approximation algorithms were known so far. In this work, we give the first constant-factor approximation algorithm. It works for both variants. The algorithm achieves an approximation ratio of 3.39 in the rectilinear plane and 4.11 in general metric spaces. We can show that our algorithm is best possible in a certain sense. We also demonstrate that our algorithm leads to improvements on real world VLSI instances compared to the currently used standard method of computing short Steiner trees.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0149-4
      Issue No: Vol. 78, No. 1 (2017)
       
  • List H-Coloring a Graph by Removing Few Vertices
    • Authors: Rajesh Chitnis; László Egri; Dániel Marx
      Pages: 110 - 146
      Abstract: In the deletion version of the list homomorphism problem, we are given graphs G and H, a list \(L(v)\subseteq V(H)\) for each vertex \(v\in V(G)\) , and an integer k. The task is to decide whether there exists a set \(W \subseteq V(G)\) of size at most k such that there is a homomorphism from \(G {\setminus } W\) to H respecting the lists. We show that DL-Hom( \({H}\) ), parameterized by k and H , is fixed-parameter tractable for any \((P_6,C_6)\) -free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom( \({H}\) ) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder et al. (Combinatorica 19(4):487–505, 1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0139-6
      Issue No: Vol. 78, No. 1 (2017)
       
  • Approximating the Maximum Overlap of Polygons under Translation
    • Authors: Sariel Har-Peled; Subhro Roy
      Pages: 147 - 165
      Abstract: Let \(P\) and \(Q\) be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present a \((1-\varepsilon )\) -approximation algorithm, for finding the translation of \(Q\) , which maximizes its area of overlap with \(P\) . Our algorithm runs in \(O\left( {c n}\right) \) time, where c is a constant that depends only on k and \(\varepsilon \) . This suggests that for polygons that are “close” to being convex, the problem can be solved (approximately), in near linear time.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0152-9
      Issue No: Vol. 78, No. 1 (2017)
       
  • A Combinatorial Certifying Algorithm for Linear Feasibility in UTVPI
           Constraints
    • Authors: K. Subramani; Piotr Wojciechowski
      Pages: 166 - 208
      Abstract: In this paper, we discuss a new combinatorial certifying algorithm for the problem of checking linear feasibility in Unit Two Variable Per Inequality (UTVPI) constraints. A UTVPI constraint has at most two non-zero variables and the coefficients of the non-zero variables belong to the set \(\{+1,\ -1\}\) . These constraints occur in a number of application domains, including but not limited to program verification, abstract interpretation, and operations research. The proposed algorithm runs in \(O(m\cdot n)\) time and \(O(m+n)\) space on a UTVPI system with n variables and m constraints. Observe that these resource bounds match the bounds of the fastest strongly polynomial algorithm for difference constraints. Inasmuch as UTVPI constraints subsume difference constraints, it is clear that the resource requirements of our algorithm are optimal. Additionally, our algorithm is certifying, in that it produces a satisfying assignment when presented with a feasible instance, and a refutation, otherwise. At the heart of our algorithm is a new constraint network representation for UTVPI constraints.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0131-1
      Issue No: Vol. 78, No. 1 (2017)
       
  • Distribution-Sensitive Construction of the Greedy Spanner
    • Authors: Sander P. A. Alewijnse; Quirijn W. Bouts; Alex P. ten Brink; Kevin Buchin
      Pages: 209 - 231
      Abstract: The greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take \(\varOmega (n^2)\) time, limiting its applicability on large data sets. We propose a novel algorithm design which uses the observation that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly. To find the usually few remaining ‘long’ edges, we use a combination of already determined local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets. We give a geometric property that holds with high probability, which in turn implies that if an edge set on these points has t-paths between pairs of points ‘close’ to each other, then it has t-paths between all pairs of points. This characterization gives an \(O(n \log ^2 n \log ^2 \log n)\) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give an \(O((n + E ) \log ^2 n \log \log n)\) expected time algorithm on uniformly distributed points that determines whether E is a t-spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0160-9
      Issue No: Vol. 78, No. 1 (2017)
       
  • Computing the Center of Uncertain Points on Tree Networks
    • Authors: Haitao Wang; Jingru Zhang
      Pages: 232 - 254
      Abstract: Uncertain data has been very common in many applications. In this paper, we consider the one-center problem for uncertain data on tree networks. In this problem, we are given a tree T and n (weighted) uncertain points each of which has m possible locations on T associated with probabilities. The goal is to find a point \(x^*\) on T such that the maximum (weighted) expected distance from \(x^*\) to all uncertain points is minimized. To the best of our knowledge, this problem has not been studied before. We propose a refined prune-and-search technique that solves the problem in linear time.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0158-3
      Issue No: Vol. 78, No. 1 (2017)
       
  • Optimization with Uniform Size Queries
    • Authors: Uriel Feige; Moshe Tennenholtz
      Pages: 255 - 273
      Abstract: Consider the problem of selecting k items that maximize the value of a monotone submodular set function f, where f can be accessed using value queries. It is well known that polynomially many queries suffice in order to obtain an approximation ratio of \(1 - \frac{1}{e}\) . We consider a variation on this problem in which the value queries are required to be of uniform size: each queried set, like the desired solution itself, must contain k items. We show that polynomially many uniform size queries suffice in order to obtain an approximation ratio of \(\frac{1}{2}\) , and that an approximation ratio of \(\frac{1 + \epsilon }{2}\) requires a number of queries that is exponential in \(\epsilon k\) . For the interesting special case of coverage functions, we show that an approximation ratio strictly better than \(\frac{1}{2}\) is attainable with polynomially many uniform size queries. The “uniform size” requirement is motivated by situations in which a firm may offer a menu of exactly k items to its clients, where k is a parameter determined by external considerations. Performing a query corresponds to physically changing the identities of the items offered, and the reply to the query is deduced by observing the behavior of clients in response to the change. Queries that involve a number of items that differs from k may not be desirable due to these external considerations. In such situations it is natural to ask whether the same approximation ratios that can be guaranteed by general value queries can also be obtained by uniform size queries.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0162-7
      Issue No: Vol. 78, No. 1 (2017)
       
  • On the Parameterized Complexity of Reconfiguration Problems
    • Authors: Amer E. Mouawad; Naomi Nishimura; Venkatesh Raman; Narges Simjour; Akira Suzuki
      Pages: 274 - 297
      Abstract: We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem \(\mathcal {Q}\) takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform S into T such that each step results in a feasible solution to \(\mathcal {Q}\) . For most of the results in this paper, S and T are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: k, a bound on the size of solutions, and \(\ell \) , a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set, all parameterized by k. In contrast, we show that reconfiguring Unbounded Hitting Set is W[2]-hard when parameterized by \(k+\ell \) . We also demonstrate the W[1]-hardness of reconfiguration variants of a large class of maximization problems parameterized by \(k+\ell \) , and of their corresponding deletion problems parameterized by \(\ell \) ; in doing so, we show that there exist problems in FPT when parameterized by k, but whose reconfiguration variants are W[1]-hard when parameterized by \(k+\ell \) .
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0159-2
      Issue No: Vol. 78, No. 1 (2017)
       
  • The Maximum Labeled Path Problem
    • Authors: Basile Couëtoux; Elie Nakache; Yann Vaxès
      Pages: 298 - 318
      Abstract: In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D, find a path in D that collects a maximum number of distinct labels. For any \(\epsilon >0\) , we provide a polynomial time approximation algorithm that computes a solution of value at least \(OPT^{1-\epsilon }\) and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX-hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless \(P=NP\) .
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0155-6
      Issue No: Vol. 78, No. 1 (2017)
       
  • Algorithms for k -Internal Out-Branching and k -Tree in Bounded Degree
           Graphs
    • Authors: Meirav Zehavi
      Pages: 319 - 341
      Abstract: In this paper, we employ the multilinear detection technique, combined with proper colorings of graphs, to develop algorithms for two problems in bounded degree graphs. We focus mostly on the k-Internal Out-Branching (k-IOB) problem, which asks if a given directed graph has an out-branching (i.e., a spanning tree with exactly one node of in-degree 0) with at least k internal nodes. The second problem, k-Tree, asks if a given undirected graph G has a (not necessarily induced) copy of a given tree T. That is, k-Tree asks whether T is a subgraph of G. We present an \(O^*(4^k)\) time randomized algorithm for k-IOB, which improves the \(O^*\) running time of the previous best known algorithm for this problem. Then, for directed graphs whose underlying (simple, undirected) graphs have bounded degree \(\varDelta \) , we modify our algorithm to solve k-IOB in time \(O^*(2^{(2-\frac{\varDelta +1}{\varDelta (\varDelta -1)})k})\) . For k- Tree in graphs of bounded degree 3, we obtain an \(O^*(1.914^k)\) time randomized algorithm. In particular, all of our algorithms use polynomial space.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0166-3
      Issue No: Vol. 78, No. 1 (2017)
       
  • Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time
           Algorithm
    • Authors: Isolde Adler; Mamadou Moustapha Kanté; O-joung Kwon
      Pages: 342 - 377
      Abstract: Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every n-vertex distance-hereditary graph, equivalently a graph of rank-width at most 1, can be computed in time \({\mathcal {O}}(n^2\cdot \log _2 n)\) , and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every n-element matroid of branch-width at most 2 can be computed in time \({\mathcal {O}}(n^2\cdot \log _2 n)\) , provided that the matroid is given by its binary representation. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50–79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of ‘limbs’ of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization.
      PubDate: 2017-05-01
      DOI: 10.1007/s00453-016-0164-5
      Issue No: Vol. 78, No. 1 (2017)
       
  • Local Computation Algorithms for Graphs of Non-constant Degrees
    • Authors: Reut Levi; Ronitt Rubinfeld; Anak Yodpinyanee
      Pages: 971 - 994
      Abstract: In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. Instead, we consider the case where parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic in n; for constant \(\varepsilon > 0\) , a randomized LCA that provides a \((1-\varepsilon )\) -approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0126-y
      Issue No: Vol. 77, No. 4 (2017)
       
  • Improved Pseudo-polynomial Bound for the Value Problem and Optimal
           Strategy Synthesis in Mean Payoff Games
    • Authors: Carlo Comin; Romeo Rizzi
      Pages: 995 - 1021
      Abstract: In this work we offer an \(O( V ^2 E \, W)\) pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor \(\log ( V \, W)\) the best previously known pseudo-polynomial time upper bound due to Brim et al. The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures.
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0123-1
      Issue No: Vol. 77, No. 4 (2017)
       
  • An On-line Competitive Algorithm for Coloring Bipartite Graphs Without
           Long Induced Paths
    • Authors: Piotr Micek; Veit Wiechert
      Pages: 1060 - 1070
      Abstract: The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for \(P_9\) -free bipartite graphs.
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0130-2
      Issue No: Vol. 77, No. 4 (2017)
       
  • Finding a Shortest Non-zero Path in Group-Labeled Graphs via Permanent
           Computation
    • Authors: Yusuke Kobayashi; Sho Toyooka
      Pages: 1128 - 1142
      Abstract: A group-labeled graph is a directed graph with each arc labeled by a group element, and the label of a path is defined as the sum of the labels of the traversed arcs. In this paper, we propose a polynomial time randomized algorithm for the problem of finding a shortest s-t path with a non-zero label in a given group-labeled graph (which we call the Shortest Non-Zero Path Problem). This problem generalizes the problem of finding a shortest path with an odd number of edges, which is known to be solvable in polynomial time by using matching algorithms. Our algorithm for the Shortest Non-Zero Path Problem is based on the ideas of Björklund and Husfeldt (Proceedings of the 41st international colloquium on automata, languages and programming, part I. LNCS 8572, pp 211–222, 2014). We reduce the problem to the computation of the permanent of a polynomial matrix modulo two. Furthermore, by devising an algorithm for computing the permanent of a polynomial matrix modulo \(2^r\) for any fixed integer r, we extend our result to the problem of packing internally-disjoint s-t paths.
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0142-y
      Issue No: Vol. 77, No. 4 (2017)
       
  • A Generalization of Multiple Choice Balls-into-Bins: Tight Bounds
    • Authors: Gahyun Park
      Pages: 1159 - 1193
      Abstract: This paper investigates a general version of the multiple choice model called the (k, d)-choice process in which n balls are assigned to n bins. In the process, \(k<d\) balls are placed into the k least loaded out of d bins chosen independently and uniformly at random in each of \(\frac{n}{k}\) rounds. The primary goal is to derive tight bounds on the maximum bin load for (k, d)-choice for any \(1 \le k < d \le n\) . Our results enable one to choose suitable parameters k and d for which the (k, d)-choice process achieves the optimal tradeoff between the maximum bin load and message cost: a constant maximum load and O(n) messages. The maximum load for a heavily loaded case where \(m>n\) balls are placed into n bins is also presented for the case \(d \ge 2k\) . Potential applications are discussed such as distributed storage as well as parallel job scheduling in a cluster.
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0141-z
      Issue No: Vol. 77, No. 4 (2017)
       
  • Efficient Indexes for Jumbled Pattern Matching with Constant-Sized
           Alphabet
    • Authors: Tomasz Kociumaka; Jakub Radoszewski; Wojciech Rytter
      Pages: 1194 - 1215
      Abstract: We introduce efficient indexes for a problem in non-standard stringology: jumbled pattern matching. An index is a data structure constructed for a text of length n over an alphabet of size \(\sigma \) that can answer queries asking if the text contains a fragment which is jumbled (Abelian) equivalent to a pattern, specified by its so-called Parikh vector. We denote the length of the pattern by m. Moosa and Rahman (J Discrete Algorithms 10:5–9, 2012) gave an index for the case of binary alphabets with \(\mathcal {O}\left( \frac{n^2}{(\log n)^2}\right) \) -time construction in the word-RAM model. Several earlier papers stated as an open problem the existence of an efficient solution for larger alphabets. In this paper we develop an index for any constant-sized alphabet. The construction involves a trade-off parameter, which in particular lets us achieve the following complexities: \(\mathcal {O}(n^{2-\delta })\) space and \(\mathcal {O}(m^{(2\sigma -1)\delta })\) query time for any \(0<\delta <1\) , or \(\mathcal {O}\left( \frac{n^2 (\log \log n)^2}{\log n}\right) \) space and polylogarithmic, \(o(\log ^{2\sigma -1} m)\) , query time. The construction time in both cases is subquadratic: \(\mathcal {O}\left( \frac{n^2 (\log \log n)^2}{\log n}\right) \) in the word-RAM model (using bit-parallelism). Our construction algorithms are randomized (Las Vegas, running time w.h.p.), which is due to the usage of perfect hashing. On the other hand, all queries are answered deterministically. A preliminary version of this work appeared at ESA 2013 (Kociumaka et al. in Algorithms, ESA 2013. LNCS, vol 8125. Springer, Berlin, pp. 625–636, 2013). Here we improve it in several ways. We achieve \(\mathcal {O}(n^2)\) -time construction of the index with \(\mathcal {O}(n^{2-\delta })\) space and \(\mathcal {O}(m^{(2\sigma -1)\delta })\) query time, which was not present in the preliminary version. We also extend the index so that the position of the leftmost occurrence of the query pattern is provided at no additional cost in the complexity; this required rather nontrivial changes in the construction algorithm.
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0140-0
      Issue No: Vol. 77, No. 4 (2017)
       
  • A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals
           with Demands
    • Authors: Rajesh Chitnis; Hossein Esfandiari; MohammadTaghi Hajiaghayi; Rohit Khandekar; Guy Kortsarz; Saeed Seddighin
      Pages: 1216 - 1239
      Abstract: Given an edge-weighted directed graph \(G=(V,E)\) on n vertices and a set \(T=\{t_1, t_2, \ldots , t_p\}\) of p terminals, the objective of the Strongly Connected Steiner Subgraph (p-SCSS) problem is to find an edge set \(H\subseteq E\) of minimum weight such that G[H] contains an \(t_{i}\rightarrow t_j\) path for each \(1\le i\ne j\le p\) . The p-SCSS problem is NP-hard, but Feldman and Ruhl [FOCS ’99; SICOMP ’06] gave a novel \(n^{O(p)}\) time algorithm. In this paper, we investigate the computational complexity of a variant of 2-SCSS where we have demands for the number of paths between each terminal pair. Formally, the \(2\) -SCSS- \((k_1, k_2)\) problem is defined as follows: given an edge-weighted directed graph \(G=(V,E)\) with weight function \(\omega : E\rightarrow {\mathbb {R}}^{\ge 0}\) , two terminal vertices s, t, and integers \(k_1, k_2\) ; the objective is to find a set of \(k_1\) paths \(F_1, F_2, \ldots , F_{k_1}\) from \(s\leadsto t\) and \(k_2\) paths \(B_1, B_2, \ldots , B_{k_2}\) from \(t\leadsto s\) such that \(\sum _{e\in E} \omega (e)\cdot \phi (e)\) is minimized, where \(\phi (e)= \max \Big \{ \{i\in [k_1] : e\in F_i\} \ ,\ \{j\in [k_2] : e\in B_j\} \Big \}\) . For each \(k\ge 1\) , we show the following: The \(2\) -SCSS- \((k,1)\) problem can be solved in time \(n^{O(k)}\) . A matching lower bound for our algorithm: the \(2\) -SCSS- \((k,1)\) problem does not have an \(f(k)\cdot n^{o(k)}\) time algorithm for any computable function f, unless the Exponential Time Hypothesis fails. Our algorithm for ...
      PubDate: 2017-04-01
      DOI: 10.1007/s00453-016-0145-8
      Issue No: Vol. 77, No. 4 (2017)
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 54.204.249.55
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016