for Journals by Title or ISSN
for Articles by Keywords

Publisher: Springer-Verlag (Total: 2355 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 2355 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: 10, SJR: 1.073, h-index: 25)
AAPS J.     Hybrid Journal   (Followers: 21, 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: 3, SJR: 0.447, h-index: 12)
Academic Psychiatry     Full-text available via subscription   (Followers: 23, SJR: 0.492, h-index: 32)
Academic Questions     Hybrid Journal   (Followers: 8, SJR: 0.135, h-index: 6)
Accreditation and Quality Assurance: J. for Quality, Comparability and Reliability in Chemical Measurement     Hybrid Journal   (Followers: 26, SJR: 0.378, h-index: 30)
Acoustical Physics     Hybrid Journal   (Followers: 11, SJR: 0.355, h-index: 20)
Acoustics Australia     Hybrid Journal  
Acta Analytica     Hybrid Journal   (Followers: 7, SJR: 0.387, h-index: 6)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1, SJR: 0.624, h-index: 34)
Acta Biotheoretica     Hybrid Journal   (Followers: 5, SJR: 0.419, h-index: 25)
Acta Diabetologica     Hybrid Journal   (Followers: 13, 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: 6)
Acta Geodaetica et Geophysica     Hybrid Journal   (Followers: 2, 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: 6, 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: 20, 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   (Followers: 1, SJR: 0.348, h-index: 27)
Acta Neuropathologica     Hybrid Journal   (Followers: 5, SJR: 6.61, h-index: 117)
Acta Oceanologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.295, h-index: 17)
Acta Parasitologica     Hybrid Journal   (Followers: 9, SJR: 0.581, h-index: 28)
Acta Physiologiae Plantarum     Hybrid Journal   (Followers: 2, SJR: 0.551, h-index: 39)
Acta Politica     Hybrid Journal   (Followers: 13, SJR: 0.658, h-index: 20)
Activitas Nervosa Superior     Hybrid Journal  
adhäsion KLEBEN & DICHTEN     Hybrid Journal   (Followers: 5, SJR: 0.103, h-index: 4)
ADHD Attention Deficit and Hyperactivity Disorders     Hybrid Journal   (Followers: 22, SJR: 0.871, h-index: 15)
Adhesion Adhesives & Sealants     Hybrid Journal   (Followers: 8)
Administration and Policy in Mental Health and Mental Health Services Research     Partially Free   (Followers: 15, SJR: 0.795, h-index: 40)
Adsorption     Hybrid Journal   (Followers: 4, SJR: 0.774, h-index: 52)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 3, SJR: 0.319, h-index: 15)
Advances in Atmospheric Sciences     Hybrid Journal   (Followers: 34, SJR: 0.959, h-index: 44)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15, SJR: 1.255, h-index: 44)
Advances in Contraception     Hybrid Journal   (Followers: 3)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 52, SJR: 1.113, h-index: 14)
Advances in Gerontology     Partially Free   (Followers: 8, SJR: 0.141, h-index: 3)
Advances in Health Sciences Education     Hybrid Journal   (Followers: 25, SJR: 1.397, h-index: 42)
Advances in Manufacturing     Hybrid Journal   (Followers: 3, SJR: 0.2, h-index: 4)
Advances in Polymer Science     Hybrid Journal   (Followers: 41, SJR: 0.637, h-index: 89)
Advances in Therapy     Hybrid Journal   (Followers: 5, SJR: 0.79, h-index: 44)
Aegean Review of the Law of the Sea and Maritime Law     Hybrid Journal   (Followers: 7)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2, SJR: 0.882, h-index: 23)
Aerobiologia     Hybrid Journal   (Followers: 2, 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: 16, 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: 13, 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: 4, SJR: 0.706, h-index: 19)
Akupunktur & Aurikulomedizin     Full-text available via subscription   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 4, 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: 8, 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: 5, SJR: 0.729, h-index: 20)
ALTEX : Alternatives to Animal Experimentation     Open Access   (Followers: 3, SJR: 1.392, h-index: 32)
AMBIO     Hybrid Journal   (Followers: 15, SJR: 1.094, h-index: 87)
American J. of Cardiovascular Drugs     Hybrid Journal   (Followers: 15, SJR: 0.864, h-index: 39)
American J. of Community Psychology     Hybrid Journal   (Followers: 25, SJR: 1.237, h-index: 83)
American J. of Criminal Justice     Hybrid Journal   (Followers: 8, SJR: 0.634, h-index: 13)
American J. of Cultural Sociology     Hybrid Journal   (Followers: 14, 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: 22, SJR: 0.293, h-index: 13)
American Sociologist     Hybrid Journal   (Followers: 14, 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: 7, SJR: 0.21, h-index: 37)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 3, SJR: 0.665, h-index: 7)
Analysis in Theory and Applications     Hybrid Journal   (Followers: 1)
Analysis of Verbal Behavior     Hybrid Journal   (Followers: 5)
Analytical and Bioanalytical Chemistry     Hybrid Journal   (Followers: 30, 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: 11)
Annals of Dyslexia     Hybrid Journal   (Followers: 10, 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: 6, 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: 15, SJR: 1.117, h-index: 62)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 8, SJR: 0.593, h-index: 42)
Annals of Microbiology     Hybrid Journal   (Followers: 10, SJR: 0.402, h-index: 26)
Annals of Nuclear Medicine     Hybrid Journal   (Followers: 5, SJR: 0.68, h-index: 45)
Annals of Operations Research     Hybrid Journal   (Followers: 10, SJR: 1.186, h-index: 78)
Annals of Ophthalmology     Hybrid Journal   (Followers: 12)
Annals of Regional Science     Hybrid Journal   (Followers: 8, SJR: 0.405, h-index: 42)
Annals of Software Engineering     Hybrid Journal   (Followers: 13)
Annals of Solid and Structural Mechanics     Hybrid Journal   (Followers: 10, SJR: 0.553, h-index: 8)
Annals of Surgical Oncology     Hybrid Journal   (Followers: 14, 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: 42, SJR: 0.575, h-index: 80)
Applied Biochemistry and Microbiology     Hybrid Journal   (Followers: 16, SJR: 0.267, h-index: 26)
Applied Cancer Research     Open Access  
Applied Categorical Structures     Hybrid Journal   (Followers: 2, SJR: 0.361, h-index: 21)
Applied Composite Materials     Hybrid Journal   (Followers: 48, SJR: 0.705, h-index: 35)
Applied Entomology and Zoology     Partially Free   (Followers: 3, SJR: 0.554, h-index: 34)
Applied Geomatics     Hybrid Journal   (Followers: 4, SJR: 0.323, h-index: 9)
Applied Geophysics     Hybrid Journal   (Followers: 8, SJR: 0.541, h-index: 13)
Applied Intelligence     Hybrid Journal   (Followers: 11, SJR: 0.777, h-index: 43)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 4, SJR: 0.358, h-index: 34)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 4, SJR: 0.955, h-index: 33)
Applied Mathematics - A J. of Chinese Universities     Hybrid Journal   (SJR: 0.275, h-index: 8)
Applied Mathematics and Mechanics     Hybrid Journal   (Followers: 5, 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: 8, SJR: 0.677, h-index: 47)
Applied Research in Quality of Life     Hybrid Journal   (Followers: 11, 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: 5, 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: 32, SJR: 0.646, h-index: 44)
Aquatic Geochemistry     Hybrid Journal   (Followers: 4, SJR: 0.764, h-index: 39)
Aquatic Sciences     Hybrid Journal   (Followers: 13, 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: 23, 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: 56, SJR: 0.804, h-index: 22)
Archive for History of Exact Sciences     Hybrid Journal   (Followers: 8, 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: 5, SJR: 0.865, h-index: 40)
Archives and Museum Informatics     Hybrid Journal   (Followers: 131)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4, SJR: 2.841, h-index: 40)
Archives of Dermatological Research     Hybrid Journal   (Followers: 7, SJR: 0.9, h-index: 65)
Archives of Environmental Contamination and Toxicology     Hybrid Journal   (Followers: 12, 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: 10, SJR: 1.198, h-index: 74)
Archives of Toxicology     Hybrid Journal   (Followers: 17, SJR: 1.595, h-index: 76)
Archives of Virology     Hybrid Journal   (Followers: 5, SJR: 1.086, h-index: 90)
Archives of Women's Mental Health     Hybrid Journal   (Followers: 14, 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: 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: 11, SJR: 0.288, h-index: 25)
Artificial Intelligence Review     Hybrid Journal   (Followers: 14, SJR: 0.948, h-index: 48)
Artificial Life and Robotics     Hybrid Journal   (Followers: 8, SJR: 0.231, h-index: 14)
Asia Europe J.     Hybrid Journal   (Followers: 5, SJR: 0.247, h-index: 9)
Asia Pacific Education Review     Hybrid Journal   (Followers: 12, SJR: 0.371, h-index: 17)
Asia Pacific J. of Management     Hybrid Journal   (Followers: 16, SJR: 1.676, h-index: 50)
Asia-Pacific Education Researcher     Hybrid Journal   (Followers: 12, 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: 8, SJR: 0.41, h-index: 10)
Asian J. of Business Ethics     Hybrid Journal   (Followers: 7)
Asian J. of Criminology     Hybrid Journal   (Followers: 5, SJR: 0.263, h-index: 8)
AStA Advances in Statistical Analysis     Hybrid Journal   (Followers: 2, SJR: 0.681, h-index: 15)
AStA Wirtschafts- und Sozialstatistisches Archiv     Hybrid Journal   (Followers: 5, SJR: 0.195, h-index: 5)
ästhetische dermatologie & kosmetologie     Full-text available via subscription  

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

Journal Cover Algorithmica
  [SJR: 0.898]   [H-I: 56]   [8 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  [2355 journals]
  • Recognizing Optimal 1-Planar Graphs in Linear Time
    • Authors: Franz J. Brandenburg
      Pages: 1 - 28
      Abstract: Abstract A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of \(4n-8\) edges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0226-8
      Issue No: Vol. 80, No. 1 (2018)
  • Induced Minor Free Graphs: Isomorphism and Clique-Width
    • Authors: Rémy Belmonte; Yota Otachi; Pascal Schweitzer
      Pages: 29 - 47
      Abstract: Abstract Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0234-8
      Issue No: Vol. 80, No. 1 (2018)
  • Near-Optimal Asymmetric Binary Matrix Partitions
    • Authors: Fidaa Abed; Ioannis Caragiannis; Alexandros A. Voudouris
      Pages: 48 - 72
      Abstract: Abstract We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (Proceedings of the 9th Conference on Web and Internet Economics (WINE), pp 1–14, 2013). Instances of the problem consist of an \(n \times m\) binary matrix A and a probability distribution over its columns. A partition scheme \(B=(B_1,\ldots ,B_n)\) consists of a partition \(B_i\) for each row i of A. The partition \(B_i\) acts as a smoothing operator on row i that distributes the expected value of each partition subset proportionally to all its entries. Given a scheme B that induces a smooth matrix \(A^B\) , the partition value is the expected maximum column entry of \(A^B\) . The objective is to find a partition scheme such that the resulting partition value is maximized. We present a 9/10-approximation algorithm for the case where the probability distribution is uniform and a \((1-1/e)\) -approximation algorithm for non-uniform distributions, significantly improving results of Alon et al. Although our first algorithm is combinatorial (and very simple), the analysis is based on linear programming and duality arguments. In our second result we exploit a nice relation of the problem to submodular welfare maximization.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0238-4
      Issue No: Vol. 80, No. 1 (2018)
  • Beyond Representing Orthology Relations by Trees
    • Authors: K. T. Huber; G. E. Scholz
      Pages: 73 - 103
      Abstract: Abstract Reconstructing the evolutionary past of a family of genes is an important aspect of many genomic studies. To help with this, simple relations on a set of sequences called orthology relations may be employed. In addition to being interesting from a practical point of view they are also attractive from a theoretical perspective in that e. g. a characterization is known for when such a relation is representable by a certain type of phylogenetic tree. For an orthology relation inferred from real biological data it is however generally too much to hope for that it satisfies that characterization. Rather than trying to correct the data in some way or another which has its own drawbacks, as an alternative, we propose to represent an orthology relation \(\delta \) in terms of a structure more general than a phylogenetic tree called a phylogenetic network. To compute such a network in the form of a level-1 representation for \(\delta \) , we formalize an orthology relation in terms of the novel concept of a symbolic 3-dissimilarity which is motivated by the biological concept of a “cluster of orthologous groups”, or COG for short. For such maps which assign symbols rather that real values to elements, we introduce the novel Network-Popping algorithm which has several attractive properties. In addition, we characterize an orthology relation \(\delta \) on some set X that has a level-1 representation in terms of eight natural properties for \(\delta \) as well as in terms of level-1 representations of orthology relations on certain subsets of X.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0241-9
      Issue No: Vol. 80, No. 1 (2018)
  • Edge-b-Coloring Trees
    • Authors: Victor Campos; Ana Silva
      Pages: 104 - 115
      Abstract: Abstract A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to at least one vertex in each other color class. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors. This problem was introduced by Irving and Manlove (Discrete Appl Math 91:127–141, 1999), where they showed that computing b(G) is \({\mathcal {NP}}\) -hard in general and polynomial-time solvable for trees. Since then, a number of complexity results were shown, including NP-hardness results for chordal graphs (Havet et al. in Discrete Appl Math 160(18):2709–2715, 2012) and line graphs (Campos et al. in Eur J Comb 48:154–164, 2015). In this article, we present a polynomial time algorithm that solves the problem restricted to claw-free block graphs, an important subclass of chordal graphs and of line graphs. This is equivalent to solving the edge coloring version restricted to trees.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0240-x
      Issue No: Vol. 80, No. 1 (2018)
  • An FPT 2-Approximation for Tree-Cut Decomposition
    • Authors: Eun Jung Kim; Sang-il Oum; Christophe Paul; Ignasi Sau; Dimitrios M. Thilikos
      Pages: 116 - 135
      Abstract: Abstract The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin Theory, Ser B, 110:47–66, 2015) with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2w, in time \(2^{O(w^2\log w)} \cdot n^2\) . Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0245-5
      Issue No: Vol. 80, No. 1 (2018)
  • 3D Rectangulations and Geometric Matrix Multiplication
    • Authors: Peter Floderus; Jesper Jansson; Christos Levcopoulos; Andrzej Lingas; Dzmitry Sledneu
      Pages: 136 - 154
      Abstract: Abstract The problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. In this paper, we first develop a 4-approximation algorithm for the special case of the problem in which P is a 3D histogram. It runs in \(O(m \log m)\) time, where m is the number of corners in P. We then apply it to exactly compute the arithmetic matrix product of two \(n \times n\) matrices A and B with nonnegative integer entries, yielding a method for computing \(A \times B\) in \(\tilde{O}(n^2 + \min \{ r_A r_B,\, n \min \{r_A,\ r_B\}\})\) time, where \(\tilde{O}\) suppresses polylogarithmic (in n) factors and where \(r_A\) and \(r_B\) denote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0247-3
      Issue No: Vol. 80, No. 1 (2018)
  • Colored Bin Packing: Online Algorithms and Lower Bounds
    • Authors: Martin Böhm; György Dósa; Leah Epstein; Jiří Sgall; Pavel Veselý
      Pages: 155 - 184
      Abstract: Abstract In the Colored Bin Packing problem a sequence of items of sizes up to 1 arrives to be packed into bins of unit capacity. Each item has one of at least two colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins. In the important special case when all items have size zero, we characterize the optimal value to be equal to color discrepancy. As our main result, we give an (asymptotically) 1.5-competitive algorithm which is optimal. In fact, the algorithm always uses at most \(\lceil 1.5\cdot OPT \rceil \) bins and we can force any deterministic online algorithm to use at least \(\lceil 1.5\cdot OPT \rceil \) bins while the offline optimum is \( OPT \) for any value of \( OPT \ge 2\) . In particular, the absolute competitive ratio of our algorithm is 5 / 3 and this is optimal. For items of arbitrary size we give a lower bound of 2.5 on the asymptotic competitive ratio of any online algorithm and an absolutely 3.5-competitive algorithm. When the items have sizes of at most 1 / d for a real \(d \ge 2\) the asymptotic competitive ratio of our algorithm is \(1.5+d/(d-1)\) . We also show that classical algorithms First Fit, Best Fit and Worst Fit are not constant competitive, which holds already for three colors and small items. In the case of two colors—the Black and White Bin Packing problem—we give a lower bound of 2 on the asymptotic competitive ratio of any online algorithm when items have arbitrary size. We also prove that all Any Fit algorithms have the absolute competitive ratio 3. When the items have sizes of at most 1 / d for a real \(d \ge 2\) we show that the Worst Fit algorithm is absolutely \((1+d/(d-1))\) -competitive.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0248-2
      Issue No: Vol. 80, No. 1 (2018)
  • Matchings with Lower Quotas: Algorithms and Complexity
    • Authors: Ashwin Arulselvan; Ágnes Cseh; Martin Groß; David F. Manlove; Jannik Matuschke
      Pages: 185 - 208
      Abstract: Abstract We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G= (A\, \dot{\cup }\, P, E)\) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between \(\textsf {NP}\) -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota \(u_{\max }\) as basis, and we prove that this dependence is necessary unless \(\textsf {FPT}= \textsf {W}[1]\) . The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee \(u_{\max }+1\) , which is asymptotically best possible unless \(\textsf {P}= \textsf {NP}\) . Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0252-6
      Issue No: Vol. 80, No. 1 (2018)
  • On the Complexity of Compressing Two Dimensional Routing Tables with Order
    • Authors: Frédéric Giroire; Frédéric Havet; Joanna Moulierac
      Pages: 209 - 233
      Abstract: Abstract Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications \(\mathcal {X}\) , which are distinct pairs \((s,t)\subseteq S\times T\) , (typically S is the set of sources and T the set of destinations), and a port function \(\pi :\mathcal {X} \rightarrow P\) where P is the set of ports. A routing list \(\mathcal {R}\) is an ordered list of triples which are of the form (s, t, p), \((*,t,p)\) , \((s,*,p)\) or \((*,*,p)\) with \(s\in S\) , \(t\in T\) and \(p\in P\) . It routes the communication (s, t) to the port \(r(s,t) =p\) which appears on the first triple in the list \(\mathcal {R}\) that is of the form (s, t, p), \((*,t,p)\) , \((s,*,p)\) or \((*,*,p)\) . If \(r(s,t)=\pi (s,t)\) , then we say that (s, t) is properly routed by \(\mathcal {R}\) and if all communications of \(\mathcal {X}\) are properly routed, we say that \(\mathcal {R}\) emulates \((\mathcal {X}, \pi )\) . The aim is to find a shortest routing list emulating \((\mathcal {X}, \pi )\) . In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication \(\mathcal {X}\) , a port function \(\pi \) and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating \((\mathcal {X}, \pi )\) of size at most k (resp. \( \mathcal {X} -k\) ). We prove that both problems a...
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0243-7
      Issue No: Vol. 80, No. 1 (2018)
  • Ham-Sandwich Cuts for Abstract Order Types
    • Authors: Stefan Felsner; Alexander Pilz
      Pages: 234 - 257
      Abstract: The linear-time ham-sandwich cut algorithm of Lo, Matoušek, and Steiger for bi-chromatic finite point sets in the plane works by appropriately selecting crossings of the lines in the dual line arrangement with a set of well-chosen vertical lines. We consider the setting where we are not given the coordinates of the point set, but only the orientation of each point triple (the order type) and give a deterministic linear-time algorithm for the mentioned sub-algorithm. This yields a linear-time ham-sandwich cut algorithm even in our restricted setting. We also show that our methods are applicable to abstract order types.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0246-4
      Issue No: Vol. 80, No. 1 (2018)
  • A Connection Between Sports and Matroids: How Many Teams Can We Beat'
    • Authors: Ildikó Schlotter; Katarína Cechlárová
      Pages: 258 - 278
      Abstract: Abstract Given an on-going sports competition, with each team having a current score and some matches left to be played, we ask whether it is possible for our distinguished team t to obtain a final standing with at most r teams finishing before t. We study the computational complexity of this problem, addressing it both from the viewpoint of parameterized complexity and of approximation. We focus on a special case equivalent to finding a maximal induced subgraph of a given graph G that admits an orientation where the in-degree of each vertex is upper-bounded by a given function. We obtain a \(\varTheta (\log V(G) )\) approximation for this problem based on an asymptotically optimal approximation we present for a certain matroid problem in which we need to cover a base of a matroid by picking elements from a set family.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0256-2
      Issue No: Vol. 80, No. 1 (2018)
  • Robust Proximity Search for Balls Using Sublinear Space
    • Authors: Sariel Har-Peled; Nirman Kumar
      Pages: 279 - 299
      Abstract: Abstract Given a set of n disjoint balls \(b_1, \dots , b_n\) in \(\mathrm{I\! R}^d\) , we provide a data structure of near linear size that can answer \((1\pm {\varepsilon })\) -approximate kth-nearest neighbor queries on the balls in \(O(\log n + 1/{\varepsilon }^d)\) time, where k and \({\varepsilon }\) may be provided at query time. If k and \({\varepsilon }\) are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0254-4
      Issue No: Vol. 80, No. 1 (2018)
  • Stretch and Diameter in Random Geometric Graphs
    • Authors: Ghurumuruhan Ganesan
      Pages: 300 - 330
      Abstract: Abstract Consider the random geometric graph \(G = G(n,r_n,f)\) consisting of n nodes independently distributed in \(S = \left[ -\frac{1}{2},\frac{1}{2}\right] ^2\) each according to a density  \(f({\cdot })\) . Two nodes u and v are joined by an edge if the Euclidean distance between them is less than \(r_n.\) Let \(C_G\) denote the component of G containing the largest number of nodes and denote \(\text {diam}(C_G)\) to be its diameter. Let s and t be the nodes of G closest to \(\left( -\frac{1}{2},\frac{1}{2}\right) \) and \(\left( \frac{1}{2},\frac{1}{2}\right) ,\) respectively and let \(d_G(s,t)\) denote their graph distance. We prove that the normalized diameter \(\frac{r_n}{\sqrt{2}} \text {diam}(C_G)\) and the stretch \(r_nd_G(s,t)\) both converge to one in probability if \(nr_n^2 \rightarrow \infty \) as \(n \rightarrow \infty \) .
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0253-5
      Issue No: Vol. 80, No. 1 (2018)
  • Profiles of PATRICIA Tries
    • Authors: Abram Magner; Wojciech Szpankowski
      Pages: 331 - 397
      Abstract: Abstract A PATRICIA trie is a trie in which non-branching paths are compressed. The external profile \(B_{n,k}\) , defined to be the number of leaves at level k of a PATRICIA trie on n nodes, is an important “summarizing” parameter, in terms of which several other parameters of interest can be formulated. Here we derive precise asymptotics for the expected value and variance of \(B_{n,k}\) , as well as a central limit theorem with error bound on the characteristic function, for PATRICIA tries on n infinite binary strings generated by a memoryless source with bias \(p > 1/2\) for \(k\sim \alpha \log n\) with \(\alpha \in (1/\log (1/q) + \varepsilon , 1/\log (1/p) - \varepsilon )\) for any fixed \(\varepsilon > 0\) . In this range, \( {\mathbb {E}}[B_{n,k}] = \varTheta ( {\mathrm {Var}}[B_{n,k}])\) , and both are of the form \(\varTheta (n^{\beta (\alpha )}/\sqrt{\log n})\) , where the \(\varTheta \) hides bounded, periodic functions in \(\log n\) whose Fourier series we explicitly determine. The compression property leads to extra terms in the Poisson functional equations for the profile which are not seen in tries or digital search trees, resulting in Mellin transforms which are only implicitly given in terms of the moments of \(B_{m,j}\) for various m and j. Thus, the proofs require information about the profile outside the main range of interest. Our derivations rely on analytic techniques, including Mellin transforms, analytic de-Poissonization, the saddle point method, and careful bounding of complex functions.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0261-5
      Issue No: Vol. 80, No. 1 (2018)
  • Simpler and Better Approximation Algorithms for the Unweighted Minimum
           Label s - t Cut Problem
    • Authors: Peng Zhang; Bin Fu; Linqing Tang
      Pages: 398 - 409
      Abstract: Abstract Given a graph \(G=(V,E)\) with a label set \(L = \{\ell _1, \ell _2, \ldots , \ell _q \}\) , in which each edge has a label from L, and a source \(s \in V\) together with a sink \(t \in V\) , the Minimum Label s-t Cut problem asks to pick a set \(L' \subseteq L\) of labels with minimized cardinality, such that the removal of all edges with labels in \(L'\) from G disconnects s and t. Let \(n = V \) and \(m = E \) . The previous best known approximation ratio for this problem in literature is \(O(m^{1/2})\) . We present two simple and purely combinatorial approximation algorithms for the problem with ratios \(O(n^{2/3}/\text {OPT}^{1/3})\) and \(O(m^{1/2} / \text {OPT}^{1/2})\) , where \(\text {OPT}\) is the optimal value of the input instance. The former result gives the first approximation ratio which is sublinear in n for the problem, and in particular applies to the instances with dense graphs (e.g., \(m = \varTheta (n^2)\) ). The latter result improves the previous ratio \(O(m^{1/2})\) , as we can always assume that \(\text {OPT}\) is a super-constant.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-016-0265-1
      Issue No: Vol. 80, No. 1 (2018)
  • Erratum to: Greedy Matching: Guarantees and Limitations
    • Authors: Bert Besser; Matthias Poloczek
      Pages: 410 - 413
      Abstract: Abstract In “Greedy Matching: Guarantees and Limitations” we erroneously claimed in Theorem 5 that no fully randomized priority algorithm for the maximum matching problem can achieve an expected approximation ratio better than  \(\frac{5}{6}\) . This bound and the provided argument hold for degree-based randomized priority algorithms. For fully randomized priority algorithms we show a  \((1 - c)\) -hardness bound for a small constant c. Thus, the central conclusion that these myopic algorithms cannot guarantee a maximum matching remains valid.
      PubDate: 2018-01-01
      DOI: 10.1007/s00453-017-0281-9
      Issue No: Vol. 80, No. 1 (2018)
  • An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast
           Matrix Multiplication
    • Authors: Carlo Comin; Romeo Rizzi
      Abstract: Abstract The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et al. (SIAM J Comput 6(3):505–517, 1977). As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e., maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama et al. showed it is O(mn). Makino and Uno (in: Hagerup, Katajainen (eds) Algorithm theory: SWAT 2004. Lecture notes in computer science, Springer, Berlin, pp 260–272, 2004) sharpened the time delay to \(O(n^{\omega })\) by generating all the children of a node in one single shot, which is performed by computing a square fast matrix multiplication. In this paper we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings’ computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of \(n^2\) nodes in one single shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from \(O(n^{2.3728639})\) to \(O(n^{2.093362})\) , keeping a polynomial work space.
      PubDate: 2018-01-02
      DOI: 10.1007/s00453-017-0402-5
  • A Polynomial Kernel for Trivially Perfect Editing
    • Authors: Pål Grønås Drange; Michał Pilipczuk
      Abstract: Abstract We give a kernel with \(O(k^7)\) vertices for Trivially Perfect Editing, the problem of adding or removing at most k edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao (Soc Netw 35(3):439–450, 2013), and by Liu et al. (Tsinghua Sci Technol 19(4):346–357, 2014). Our general technique implies also the existence of kernels of the same size for related Trivially Perfect Completion and Trivially Perfect Deletion problems. Whereas for the former an \(O(k^3)\) kernel was given by Guo (in: ISAAC 2007, LNCS, vol 4835, Springer, pp 915–926, 2007), for the latter no polynomial kernel was known. We complement our study of Trivially Perfect Editing by proving that, contrary to Trivially Perfect Completion, it cannot be solved in time \(2^{o(k)}\cdot n^{O(1)}\) unless the exponential time hypothesis fails. In this manner we complete the picture of the parameterized and kernelization complexity of the classic edge modification problems for the class of trivially perfect graphs.
      PubDate: 2017-12-28
      DOI: 10.1007/s00453-017-0401-6
  • The Densest Subgraph Problem with a Convex/Concave Size Function
    • Authors: Yasushi Kawase; Atsushi Miyauchi
      Abstract: Abstract In the densest subgraph problem, given an edge-weighted undirected graph \(G=(V,E,w)\) , we are asked to find \(S\subseteq V\) that maximizes the density, i.e., w(S) /  S , where w(S) is the sum of weights of the edges in the subgraph induced by S. This problem has often been employed in a wide variety of graph mining applications. However, the problem has a drawback; it may happen that the obtained subset is too large or too small in comparison with the size desired in the application at hand. In this study, we address the size issue of the densest subgraph problem by generalizing the density of \(S\subseteq V\) . Specifically, we introduce the f-density of \(S\subseteq V\) , which is defined as w(S) / f( S ), where \(f:\mathbb {Z}_{\ge 0}\rightarrow \mathbb {R}_{\ge 0}\) is a monotonically non-decreasing function. In the f-densest subgraph problem (f-DS), we aim to find \(S\subseteq V\) that maximizes the f-density w(S) / f( S ). Although f-DS does not explicitly specify the size of the output subset of vertices, we can handle the above size issue using a convex/concave size function f appropriately. For f-DS with convex function f, we propose a nearly-linear-time algorithm with a provable approximation guarantee. On the other hand, for f-DS with concave function f, we propose an LP-based exact algorithm, a flow-based \(O( V ^3)\) -time exact algorithm for unweighted graphs, and a nearly-linear-time approximation algorithm.
      PubDate: 2017-12-20
      DOI: 10.1007/s00453-017-0400-7
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