for Journals by Title or ISSN
for Articles by Keywords
help

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

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

Journal Cover
Algorithmica
Journal Prestige (SJR): 0.56
Citation Impact (citeScore): 1
Number of Followers: 9  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1432-0541 - ISSN (Online) 0178-4617
Published by Springer-Verlag Homepage  [2351 journals]
  • Preface to Special Issue Dedicated to the 60th Birthday of Gregory Gutin
    • Authors: Fedor V. Fomin; Saket Saurabh
      Pages: 2513 - 2515
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-018-0416-7
      Issue No: Vol. 80, No. 9 (2018)
       
  • Editor’s Note: Special Issue Dedicated to the 60th Birthday of
           Gregory Gutin
    • Pages: 2516 - 2516
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-018-0437-2
      Issue No: Vol. 80, No. 9 (2018)
       
  • Clustering with Lower-Bounded Sizes
    • Authors: Faisal N. Abu-Khzam; Cristina Bazgan; Katrin Casel; Henning Fernau
      Pages: 2517 - 2550
      Abstract: Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for \(k=2\) with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k.
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-017-0374-5
      Issue No: Vol. 80, No. 9 (2018)
       
  • Stable Matching Games: Manipulation via Subgraph Isomorphism
    • Authors: Sushmita Gupta; Sanjukta Roy
      Pages: 2551 - 2573
      Abstract: In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the Stable Extension of Partial Matching (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale–Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui (Algorithmica 58:151–169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time \(2^{{\mathcal {O}} (n)}\) , where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time \(2^{o(n)}\) . Our algorithm is a non-trivial combination of a parameterized algorithm for Subgraph Isomorphism, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete.
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-017-0382-5
      Issue No: Vol. 80, No. 9 (2018)
       
  • Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
    • Authors: Michael Etscheid; Matthias Mnich
      Pages: 2574 - 2615
      Abstract: The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015) for (Signed) Max-Cut Above Edwards−Erd ő s Bound can be implemented so as to run in linear time \(8^k\cdot O(m)\) ; this significantly improves the previous analysis with run time \(8^k\cdot O(n^4)\) . We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards−Erd ő s Bound with O(k) vertices, improving a kernel with  \(O(k^3)\) vertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013). We improve all known kernels for parameterizations above strongly \(\lambda \) -extendible properties (a generalization of the Max-Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from  \(O(k^3)\) vertices to O(k) vertices. Therefore, Max Acyclic Subdigraph parameterized above Poljak–Turzík bound admits a kernel with O(k) vertices and can be solved in  \(2^{O(k)}\cdot n^{O(1)}\) time; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012). All presented kernels can be computed in time O(km).
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-017-0388-z
      Issue No: Vol. 80, No. 9 (2018)
       
  • Fréchet Distance Between a Line and Avatar Point Set
    • Authors: Aritra Banik; Fahad Panolan; Venkatesh Raman; Vibha Sahlot
      Pages: 2616 - 2636
      Abstract: Frèchet distance is an important geometric measure that captures the distance between two curves or more generally point sets. In this paper, we consider a natural variant of Fréchet distance problem with multiple choice, provide an approximation algorithm and address its parameterized and kernelization complexity. A multiple choice problem consists of a set of color classes \(\mathcal {Q}=\{Q_1,Q_2,\ldots ,Q_n\}\) , where each class \(Q_i\) consists of a pair of points \(Q_i = \{q_i, \bar{q_i}\}\) . We call a subset \(A\subset \{q_i , \bar{q_i}:1\le i\le n\}\) conflict-free if A contains at most one point from each color class. The standard objective in multiple choice problem is to select a conflict-free subset that optimizes a given function. Given a line-segment \(\ell \) and a set \(\mathcal {Q}\) of a pair of points in \(\mathbb {R}^2\) , our objective is to find a conflict-free subset that minimizes the Fréchet distance between \(\ell \) and the point set, where the minimum is taken over all possible conflict-free subsets. We first show that this problem is NP-hard, and provide a 3-approximation algorithm. Then we develop a simple randomized FPT algorithm for the problem when parametrized by the solution size, which is later derandomized using universal family of sets. We believe that our derandomization technique can be of independent interest, and can be used to solve other parameterized multiple choice problems. The randomized algorithm runs in \(\mathcal {O}(2^k n \log ^2 n)\) time, and the derandomized deterministic algorithm runs in \(2^k k^{\mathcal {O}(\log k)} n \log ^2 n\) time, where k, the parameter, is the number of elements in the conflict-free subset solution. Finally we present a simple branching algorithm for the problem running in \(\mathcal {O}(2^k n\log n)\) time. We also show that the problem does not have a polynomial sized kernel under standard complexity theoretic assumptions.
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-017-0352-y
      Issue No: Vol. 80, No. 9 (2018)
       
  • Dynamic Parameterized Problems
    • Authors: R. Krithika; Abhishek Sahu; Prafullkumar Tale
      Pages: 2637 - 2655
      Abstract: We study the parameterized complexity of various graph theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties. In real world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size k of the symmetric difference of the edge sets of the two graphs (on n vertices) and the size r of the symmetric difference of the two solutions. We study the Dynamic \(\Pi \) -Deletion problem which is the dynamic variant of the classical \(\Pi \) -Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of Dynamic \(\Pi \) -Deletion such as Dynamic Vertex Cover and Dynamic Feedback Vertex Set, we describe improved algorithms and linear kernels. Specifically, we show that Dynamic Vertex Cover has a deterministic algorithm with \(1.0822^k n^{\mathcal {O}(1)}\) running time and Dynamic Feedback Vertex Set has a randomized algorithm with \(1.6667^k n^{\mathcal {O}(1)}\) running time. We also show that Dynamic Connected Feedback Vertex Set can be solved in \(2^{\mathcal {O}(k)} n^{\mathcal {O}(1)}\) time. For each of Dynamic Connected Vertex Cover, Dynamic Dominating Set and Dynamic Connected Dominating Set, we describe an algorithm with \(2^k n^{\mathcal {O}(1)}\) running time and show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture.
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-017-0349-6
      Issue No: Vol. 80, No. 9 (2018)
       
  • Structural Parameterizations of Undirected Feedback Vertex Set: FPT
           Algorithms and Kernelization
    • Authors: Diptapriyo Majumdar; Venkatesh Raman
      Pages: 2683 - 2724
      Abstract: A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the ‘deletion set’. In this paper, we show that FVS is fixed-parameter tractable by an \({{\mathcal {O}}}(2^k n^{{{\mathcal {O}}}(1)})\) time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time \({{\mathcal {O}}}((\sqrt{2} - \epsilon )^k n^{{{\mathcal {O}}}(1)})\) is not possible unless SETH fails. When parameterized by k, the number of vertices, whose deletion results in a split graph, we give an \({{\mathcal {O}}}(3.148^k n^{{{\mathcal {O}}}(1)})\) time algorithm. When parameterized by k, the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an \({{\mathcal {O}}}(5^k n^{{{\mathcal {O}}}(1)})\) algorithm. Regarding kernelization results, we show that When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, FVS has an \({{\mathcal {O}}}(k^7)\) vertices kernel improving from the previously known \({{\mathcal {O}}}(k^{10})\) bound. When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel with \({{\mathcal {O}}}(k^{3d+3})\) vertices. We also prove a lower bound of \(\varOmega (k^{d+2})\) size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles.
      PubDate: 2018-09-01
      DOI: 10.1007/s00453-018-0419-4
      Issue No: Vol. 80, No. 9 (2018)
       
  • A Moderately Exponential Time Algorithm for k -IBDD Satisfiability
    • Authors: Atsuki Nagao; Kazuhisa Seto; Junichi Teruyama
      Pages: 2725 - 2741
      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: 2018-10-01
      DOI: 10.1007/s00453-017-0332-2
      Issue No: Vol. 80, No. 10 (2018)
       
  • A Clustering-Based Approach to Kinetic Closest Pair
    • Authors: Zahed Rahmati; Timothy M. Chan
      Pages: 2742 - 2756
      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: 2018-10-01
      DOI: 10.1007/s00453-017-0338-9
      Issue No: Vol. 80, No. 10 (2018)
       
  • Rank Reduction of Oriented Graphs by Vertex and Edge Deletions
    • Authors: Syed M. Meesum; Saket Saurabh
      Pages: 2757 - 2776
      Abstract: In this paper we continue our study of graph modification problems defined by reducing the rank of the adjacency matrix of the given graph, and extend our results from undirected graphs to modifying the rank of skew-adjacency matrix of oriented graphs. An instance of a graph modification problem takes as input a graph G and a positive integer k, and the objective is to either delete k vertices/edges or edit k edges so that the resulting graph belongs to a particular family \(\mathcal{F}\) of graphs. Given a fixed positive integer r, we define \(\mathcal{F}_r\) as the family of oriented graphs where for each \(G\in \mathcal{F}_r\) , the rank of the skew-adjacency matrix of G is at most r. Using the family \(\mathcal{F}_r\) we do algorithmic study, both in classical and parameterized complexity, of the following graph modification problems: \(r\) -Rank Vertex Deletion, \(r\) -Rank Edge Deletion. We first show that both the problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time \(2^{\mathcal{O}(k \log r)}n^{\mathcal{O}(1)}\) for \(r\) -Rank Vertex Deletion, and an algorithm for \(r\) -Rank Edge Deletion running in time \(2^{\mathcal{O}(f(r) \sqrt{k} \log k )}n^{\mathcal{O}(1)}\) . In addition to our FPT results we design polynomial kernels for these problems. Our main structural result, which is the fulcrum of all our algorithmic results, is that for a fixed integer r the size of any “reduced graph” in \(\mathcal{F}_r\) is upper bounded by \(3^r\) . This result is of independent interest and generalizes a similar result of Kotlov and Lovász regarding reduced oriented graphs of rank r.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0340-2
      Issue No: Vol. 80, No. 10 (2018)
       
  • Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and
           LP-based Approximation Algorithms
    • Authors: Riley Murray; Samir Khuller; Megan Chao
      Pages: 2777 - 2798
      Abstract: The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m “subjobs” and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0345-x
      Issue No: Vol. 80, No. 10 (2018)
       
  • Upper Domination: Towards a Dichotomy Through Boundary Properties
    • Authors: Hassan AbouEisha; Shahid Hussain; Vadim Lozin; Jérôme Monnot; Bernard Ries; Viktor Zamaraev
      Pages: 2799 - 2817
      Abstract: An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0346-9
      Issue No: Vol. 80, No. 10 (2018)
       
  • The A Priori Traveling Repairman Problem
    • Authors: Martijn van Ee; René Sitters
      Pages: 2818 - 2833
      Abstract: The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0351-z
      Issue No: Vol. 80, No. 10 (2018)
       
  • The Induced Separation Dimension of a Graph
    • Authors: Emile Ziedan; Deepak Rajendraprasad; Rogers Mathew; Martin Charles Golumbic; Jérémie Dusart
      Pages: 2834 - 2848
      Abstract: A linear ordering of the vertices of a graph G separates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges \(\{a,b\}\) and \(\{c,d\}\) of G strongly independent if the set of endpoints \(\{a,b,c,d\}\) induces a \(2K_2\) in G. The induced separation dimension of a graph G is the smallest cardinality of a family \(\mathcal {L}\) of linear orders of V(G) such that every pair of strongly independent edges in G are separated in at least one of the linear orders in \(\mathcal {L}\) . For each \(k \in \mathbb {N}\) , the family of graphs with induced separation dimension at most k is denoted by \({\text {ISD}}(k)\) . In this article, we initiate a study of this new dimensional parameter. The class \({\text {ISD}}(1)\) or, equivalently, the family of graphs which can be embedded on a line so that every pair of strongly independent edges are disjoint line segments, is already an interesting case. On the positive side, we give characterizations for chordal graphs in \({\text {ISD}}(1)\) which immediately lead to a polynomial time algorithm which determines the induced separation dimension of chordal graphs. On the negative side, we show that the recognition problem for \({\text {ISD}}(1)\) is NP-complete for general graphs. Nevertheless, we show that the maximum induced matching problem can be solved efficiently in \({\text {ISD}}(1)\) . We then briefly study \({\text {ISD}}(2)\) and show that it contains many important graph classes like outerplanar graphs, chordal graphs, circular arc graphs and polygon-circle graphs. Finally, we describe two techniques to construct graphs with large induced separation dimension. The first one is used to show that the maximum induced separation dimension of a graph on n vertices is \(\Theta (\lg n)\) and the second one is used to construct AT-free graphs with arbitrarily large induced separation dimension. The second construction is also used to show that, for every \(k \ge 2\) , the recognition problem for \({\text {ISD}}(k)\) is NP-complete even on AT-free graphs.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0353-x
      Issue No: Vol. 80, No. 10 (2018)
       
  • Dual-Based Approximation Algorithms for Cut-Based Network Connectivity
           Problems
    • Authors: Benjamin Grimmer
      Pages: 2849 - 2873
      Abstract: We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives a 3/2-approximation to Minimum 2-Edge-Connected Spanning Subgraph that is equivalent to a previously proposed algorithm. One well-studied branch of network design models ad hoc networks where each node can either operate at high or low power. If we allow unidirectional links, we can formalize this into the problem Dual Power Assignment (DPA). Our dual-based approach gives a 3 / 2-approximation to DPA, improving the previous best approximation known of \(11/7\approx 1.57\) . Another standard network design problem is Minimum Strongly Connected Spanning Subgraph (MSCS). We propose a new problem generalizing MSCS and DPA called Star Strong Connectivity (SSC). Then we show that our dual-based approach achieves a 1.6-approximation ratio on SSC. As a consequence of our dual-based approximations, we prove new upper bounds on the integrality gaps of these problems.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0356-7
      Issue No: Vol. 80, No. 10 (2018)
       
  • The Ordered Covering Problem
    • Authors: Uriel Feige; Yael Hitron
      Pages: 2874 - 2908
      Abstract: We study the Ordered Covering (OC) problem. The input is a finite set of n elements X, a color function \(c:X \rightarrow \{0,1\}\) and a collection \(\mathcal {S}\) of subsets of X. A solution consists of an ordered tuple \(T=(S_1,\dots ,S_{\ell })\) of sets from \(\mathcal {S}\) which covers X, and a coloring \(g:\{S_i\}_{i=1}^\ell \rightarrow \{0,1\}\) such that \(\forall x \in X\) , the first set covering x in the tuple, namely \(S_j\) with \(j=\min \{i : x \in S_i\}\) , has color \(g(S_j)=c(x)\) . The minimization version is to find a solution using the minimum number of sets. Variants of OC include OC \((\alpha _0,\alpha _1)\) in which each element of color \(i \in \{0,1\}\) appears in at most \(\alpha _i\) sets of \(\mathcal {S}\) , and k–OC in which the first set of the solution \(S_1\) is required to have color 0, and there are at most \(k-1\) alternations of colors in the solution. Among other results we show: There is a polynomial time approximation algorithm for Min–OC(2, 2) with approximation ratio 2. (This is best possible unless Vertex Cover can be approximated within a ratio better than 2.) Moreover, Min–OC(2, 2) can be solved optimally in polynomial time if the underlying instance is bipartite. For every \(\alpha _0, \alpha _1 \ge 2\) , there is a polynomial time approximation algorithm for Min–3–OC \((\alpha _0,\alpha _1)\) with approximation \(\alpha _1(\alpha _0 - 1)\) . Unless the unique games conjecture is false, this is best possible.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0357-6
      Issue No: Vol. 80, No. 10 (2018)
       
  • Complexity of Secure Sets
    • Authors: Bernhard Bliem; Stefan Woltran
      Pages: 2909 - 2940
      Abstract: A secure set S in a graph is defined as a set of vertices such that for any \(X\subseteq S\) the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is \(\mathrm {\text {co-}NP}\) -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph G and integer k, a non-empty secure set for G of size at most k exists. In this work, we pinpoint the complexity of this problem by showing that it is \(\mathrm {\Sigma ^P_2}\) -complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is \(\mathrm {W[1]}\) -hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and “subset problems” that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in \(\mathrm {XP}\) , and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0358-5
      Issue No: Vol. 80, No. 10 (2018)
       
  • Clique Clustering Yields a PTAS for Max-Coloring Interval Graphs
    • Authors: Tim Nonner
      Pages: 2941 - 2956
      Abstract: We are given an interval graph \( G = (V,E) \) where each interval \( I \in V\) has a weight \( w_I \in \mathbb {Q}^+ \) . The goal is to color the intervals \( V\) with an arbitrary number of color classes \( C_1, C_2, \ldots , C_k \) such that \( \sum _{i=1}^k \max _{I \in C_i} w_I \) is minimized. This problem, called max-coloring interval graphs or weighted coloring interval graphs, contains the classical problem of coloring interval graphs as a special case for uniform weights, and it arises in many practical scenarios such as memory management. Pemmaraju, Raman, and Varadarajan showed that max-coloring interval graphs is NP-hard [21] and presented a 2-approximation algorithm. We settle the approximation complexity of this problem by giving a polynomial-time approximation scheme (PTAS), that is, we show that there is an \( (1+\epsilon ) \) -approximation algorithm for any \( \epsilon > 0 \) . The PTAS also works for the bounded case where the sizes of the color classes are bounded by some arbitrary \( k \le n \) .
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0362-9
      Issue No: Vol. 80, No. 10 (2018)
       
  • A Note on Submodular Function Minimization with Covering Type Linear
           Constraints
    • Authors: Naoyuki Kamiyama
      Pages: 2957 - 2971
      Abstract: In this paper, we consider the non-negative submodular function minimization problem with covering type linear constraints. Assume that there exist m linear constraints, and we denote by \(\varDelta _i\) the number of non-zero coefficients in the ith constraints. Furthermore, we assume that \(\varDelta _1 \ge \varDelta _2 \ge \cdots \ge \varDelta _m\) . For this problem, Koufogiannakis and Young proposed a polynomial-time \(\varDelta _1\) -approximation algorithm. In this paper, we propose a new polynomial-time primal-dual approximation algorithm based on the approximation algorithm of Takazawa and Mizuno for the covering integer program with \(\{0,1\}\) -variables and the approximation algorithm of Iwata and Nagano for the submodular function minimization problem with set covering constraints. The approximation ratio of our algorithm is \(\max \{\varDelta _2, \min \{\varDelta _1, 1 + \varPi \}\}\) , where \(\varPi \) is the maximum size of a connected component of the input submodular function.
      PubDate: 2018-10-01
      DOI: 10.1007/s00453-017-0363-8
      Issue No: Vol. 80, No. 10 (2018)
       
 
 
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.198.170.159
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-