for Journals by Title or ISSN
for Articles by Keywords

Publisher: Springer-Verlag (Total: 2349 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 2349 Journals sorted alphabetically
3D Printing in Medicine     Open Access   (Followers: 1)
3D Research     Hybrid Journal   (Followers: 20, 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: 21, SJR: 1.118, CiteScore: 4)
AAPS PharmSciTech     Hybrid Journal   (Followers: 7, SJR: 0.752, CiteScore: 3)
Abdominal Imaging     Hybrid Journal   (Followers: 15, 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: 26, 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: 27, 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: 7, SJR: 0.24, CiteScore: 1)
Acta Geodaetica et Geophysica     Hybrid Journal   (Followers: 2, SJR: 0.305, CiteScore: 1)
Acta Geophysica     Hybrid Journal   (Followers: 10, SJR: 0.312, 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: 4, SJR: 7.589, CiteScore: 12)
Acta Oceanologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.334, CiteScore: 1)
Acta Physiologiae Plantarum     Hybrid Journal   (Followers: 2, SJR: 0.574, CiteScore: 2)
Acta Politica     Hybrid Journal   (Followers: 15, SJR: 0.605, CiteScore: 1)
Activitas Nervosa Superior     Hybrid Journal   (SJR: 0.147, CiteScore: 0)
adhäsion KLEBEN & DICHTEN     Hybrid Journal   (Followers: 8, SJR: 0.103, CiteScore: 0)
ADHD Attention Deficit and Hyperactivity Disorders     Hybrid Journal   (Followers: 24, 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: 17, 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: 55, 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: 4, SJR: 0.475, CiteScore: 2)
Advances in Polymer Science     Hybrid Journal   (Followers: 45, 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: 18, 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: 6, SJR: 0.276, CiteScore: 1)
Agriculture and Human Values     Hybrid Journal   (Followers: 14, SJR: 1.173, CiteScore: 3)
Agroforestry Systems     Hybrid Journal   (Followers: 20, 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: 29, 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: 14, 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: 6)
Analytical and Bioanalytical Chemistry     Hybrid Journal   (Followers: 31, SJR: 0.978, CiteScore: 3)
Anatomical Science Intl.     Hybrid Journal   (Followers: 3, 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: 17, 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: 13, SJR: 0.413, CiteScore: 1)
Annals of Microbiology     Hybrid Journal   (Followers: 11, 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: 12)
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: 44, SJR: 0.571, CiteScore: 2)
Applied Biochemistry and Microbiology     Hybrid Journal   (Followers: 18, SJR: 0.21, CiteScore: 1)
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: 4, 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: 9, 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: 66, SJR: 1.182, CiteScore: 4)
Applied Physics A     Hybrid Journal   (Followers: 10, 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: 19, SJR: 0.225, CiteScore: 0)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 5, SJR: 0.542, CiteScore: 1)
Aquaculture Intl.     Hybrid Journal   (Followers: 25, SJR: 0.591, CiteScore: 2)
Aquarium Sciences and Conservation     Hybrid Journal   (Followers: 2)
Aquatic Ecology     Hybrid Journal   (Followers: 35, 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: 21, 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: 63, SJR: 0.745, CiteScore: 2)
Archive for History of Exact Sciences     Hybrid Journal   (Followers: 7, SJR: 0.186, CiteScore: 1)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 3, 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: 145, 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: 9, 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: 15, 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: 6, 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: 16, 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: 6, 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  
Astronomy and Astrophysics Review     Hybrid Journal   (Followers: 22, SJR: 3.385, CiteScore: 5)

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

Journal Cover
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  [2349 journals]
  • The Densest Subgraph Problem with a Convex/Concave Size Function
    • Authors: Yasushi Kawase; Atsushi Miyauchi
      Pages: 3461 - 3480
      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: 2018-12-01
      DOI: 10.1007/s00453-017-0400-7
      Issue No: Vol. 80, No. 12 (2018)
  • A Polynomial Kernel for Trivially Perfect Editing
    • Authors: Pål Grønås Drange; Michał Pilipczuk
      Pages: 3481 - 3524
      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: 2018-12-01
      DOI: 10.1007/s00453-017-0401-6
      Issue No: Vol. 80, No. 12 (2018)
  • An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast
           Matrix Multiplication
    • Authors: Carlo Comin; Romeo Rizzi
      Pages: 3525 - 3562
      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-12-01
      DOI: 10.1007/s00453-017-0402-5
      Issue No: Vol. 80, No. 12 (2018)
  • Quantifying Competitiveness in Paging with Locality of Reference
    • Authors: Susanne Albers; Dario Frascaria
      Pages: 3563 - 3596
      Abstract: The classical paging problem is to maintain a two-level memory system so that a sequence of requests to memory pages can be served with a small number of faults. Standard competitive analysis gives overly pessimistic results as it ignores the fact that real-world input sequences exhibit locality of reference. Initiated by a paper of Borodin et al. (J Comput Syst Sci 50:244–258, 1995) there has been considerable research interest in paging with locality of reference. In this paper we study the paging problem using an intuitive and simple locality model that records inter-request distances in the input. A characteristic vector \(\mathcal{C}\) defines a class of request sequences with certain properties on these distances. The concept was introduced by Panagiotou and Souza (In: Proceedings of 38th annual ACM symposium on theory of computing (STOC), 2006). As a main contribution we develop new and improved bounds on the performance of important paging algorithms. A strength and novelty of the results is that they express algorithm performance in terms of locality parameters. In a first step we develop a new lower bound on the number of page faults incurred by an optimal offline algorithm opt. The bound is tight up to a small additive constant. Technically, the result relies on a new approach of relating the number of page faults to the number of memory hits and amortizing suitably. Based on these expressions for opt’s cost, we obtain nearly tight upper and lower bounds on lru’s competitiveness, given any characteristic vector \(\mathcal{C}\) . Furthermore, we compare lru to fifo and fwf. For the first time we show bounds that quantify the difference between lru’s performance and that of the other two strategies. The results imply that lru is strictly superior on inputs with a high degree of locality of reference. There exist general input families for which lru achieves constant competitive ratios whereas the guarantees of fifo and fwf tend to k, the size of the fast memory. Finally, we report on an experimental study that demonstrates that our theoretical bounds are very close to the experimentally observed ones. Hence our contributions bring competitive paging again closer to practice.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0406-9
      Issue No: Vol. 80, No. 12 (2018)
  • Parameterized Complexity of Length-bounded Cuts and Multicuts
    • Authors: Pavel Dvořák; Dušan Knop
      Pages: 3597 - 3617
      Abstract: We study the Minimum Length-Bounded Cut problem where the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least \(L + 1\) long. We show the problem can be computed in \(\mathsf {FPT}\) time with respect to L and the tree-width of the input graph G as parameters and with linear dependence of V(G) (i.e., in time \(f (L, {\text {tw}}(G)) V(G) \) for a computable function f). We derive an \(\mathsf {FPT}\) algorithm for a more general multi-commodity length-bounded cut problem when additionally parameterized by the number of terminals. For the former problem we show a \(\mathsf {W}[1]\) -hardness result when the parameterization is done by the path-width only (instead of the tree-width) and that this problem does not admit polynomial kernel when parameterized by path-width and L. We also derive an \(\mathsf {FPT}\) algorithm for the Minimum Length-Bounded Cut problem when parameterized by the tree-depth, thus showing an interesting behavior for this problem and parameters tree-depth and path-width.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0408-7
      Issue No: Vol. 80, No. 12 (2018)
  • The Sandwich Problem for Decompositions and Almost Monotone Properties
    • Authors: Maria Chudnovsky; Celina M. H. de Figueiredo; Sophie Spirkl
      Pages: 3618 - 3645
      Abstract: We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in \({\mathcal {C}}\) as an induced subgraph is almost monotone if \({\mathcal {C}}\) is the set of thetas, the set of pyramids, or the set of prisms and thetas. We show that the property of containing a hole of length \(\equiv j \mod n\) is almost monotone if and only if \(j \equiv 2 \mod n\) or \(n \le 2\) . Moreover, we show that the imperfect graph sandwich problem, also known as the Berge trigraph recognition problem, can be solved in polynomial time. We also study the complexity of several graph decompositions related to perfect graphs, namely clique cutset, (full) star cutset, homogeneous set, homogeneous pair, and 1-join, with respect to the partitioned and unpartitioned probe problems. We show that the clique cutset and full star cutset unpartitioned probe problems are NP-hard. We show that for these five decompositions, the partitioned probe problem is in P, and the homogeneous set, 1-join, 1-join in the complement, and full star cutset in the complement unpartitioned probe problems can be solved in polynomial time as well.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0409-6
      Issue No: Vol. 80, No. 12 (2018)
  • Canonical Representations for Circular-Arc Graphs Using Flip Sets
    • Authors: Maurice Chandoo
      Pages: 3646 - 3672
      Abstract: We show that computing canonical representations for circular-arc (CA) graphs reduces to computing certain subsets of vertices called flip sets. For a broad class of CA graphs, which we call uniform, it suffices to compute a CA representation to find such flip sets. As a consequence canonical representations for uniform CA graphs can be obtained in polynomial-time. We then investigate what kind of CA graphs pose a challenge to this approach. This leads us to introduce the notion of restricted CA matrices and show that the canonical representation problem for CA graphs is logspace-reducible to that of restricted CA matrices. As a byproduct, we obtain the result that CA graphs without induced 4-cycles can be canonized in logspace.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0410-0
      Issue No: Vol. 80, No. 12 (2018)
  • Self-Stabilizing Balls and Bins in Batches
    • Authors: Petra Berenbrink; Tom Friedetzky; Peter Kling; Frederik Mallmann-Trenn; Lars Nagel; Chris Wastell
      Pages: 3673 - 3703
      Abstract: A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where m balls (tasks) are to be distributed among n bins (servers). In a seminal work, Azar et al. (SIAM J Comput 29(1):180–200, 1999. proposed the sequential strategy \(\textsc {Greedy}[{d}]\) for \(n=m\) . Each ball queries the load of d random bins and is allocated to a least loaded of them. Azar et al. (1999) showed that \(d=2\) yields an exponential improvement compared to \(d=1\) . Berenbrink et al. (SIAM J Comput 35(6):1350–1385, 2006. extended this to \(m\gg n\) , showing that for \(d=2\) the maximal load difference is independent of m (in contrast to the \(d=1\) case). We propose a new variant of an infinite balls-into-bins process. In each round an expected number of \(\lambda n\) new balls arrive and are distributed (in parallel) to the bins. Subsequently, each non-empty bin deletes one of its balls. This setting models a set of servers processing incoming requests, where clients can query a server’s current load but receive no information about parallel requests. We study the \(\textsc {Greedy}[{d}]\) distribution scheme in this setting and show a strong self-stabilizing property: for any arrival rate \(\lambda =\lambda (n)<1\) , the system load is time-invariant. Moreover, for any (even super-exponential) round t, the maximum system load is (w.h.p.) for \(d=1\) and for \(d=2\) . In particular, \(\textsc {Greedy}[{2}]\) has an exponentially smaller system load for high arrival rates.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0411-z
      Issue No: Vol. 80, No. 12 (2018)
  • Not-All-Equal and 1-in-Degree Decompositions: Algorithmic Complexity and
    • Authors: Ali Dehghan; Mohammad-Reza Sadeghi; Arash Ahadi
      Pages: 3704 - 3727
      Abstract: A Not-All-Equal decomposition of a graph G is a decomposition of the vertices of G into two parts such that each vertex in G has at least one neighbor in each part. Also, a 1-in-Degree decomposition of a graph G is a decomposition of the vertices of G into two parts A and B such that each vertex in the graph G has exactly one neighbor in part A. Among our results, we show that for a given graph G, if G does not have any cycle of length congruent to 2 mod 4, then there is a polynomial time algorithm to decide whether G has a 1-in-Degree decomposition. In sharp contrast, we prove that for every r, \(r\ge 3\) , for a given r-regular bipartite graph G determining whether G has a 1-in-Degree decomposition is \( \mathbf {NP} \) -complete. These complexity results have been especially useful in proving \( \mathbf {NP} \) -completeness of various graph related problems for restricted classes of graphs. In consequence of these results we show that for a given bipartite 3-regular graph G determining whether there is a vector in the null-space of the 0,1-adjacency matrix of G such that its entries belong to \(\{ \pm \, 1,\pm \,2\}\) is \(\mathbf {NP} \) -complete. Among other results, we introduce a new version of Planar 1-in-3 SAT and we prove that this version is also \( \mathbf {NP} \) -complete. In consequence of this result, we show that for a given planar (3, 4)-semiregular graph G determining whether there is a vector in the null-space of the 0,1-incidence matrix of G such that its entries belong to \(\{ \pm \,1,\pm \,2\}\) is \(\mathbf {NP} \) -complete.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0412-y
      Issue No: Vol. 80, No. 12 (2018)
  • Dynamic Path Queries in Linear Space
    • Authors: Meng He; J. Ian Munro; Gelin Zhou
      Pages: 3728 - 3765
      Abstract: In the path reporting problem, we preprocess a tree on n nodes each of which is assigned a weight, such that given an arbitrary path and a weight range, we can report the nodes whose weights are within the range. We consider this problem in dynamic settings, and propose the first non-trivial linear-space solution that supports path reporting in \(O((\lg n{/}\lg \lg n)^2 + occ \lg n{/}\lg \lg n)\) time, where occ is the output size, and the insertion and deletion of a node of an arbitrary degree in \(O(\lg ^{2+\epsilon } n)\) amortized time, for any constant \(\epsilon \in (0, 1)\) . Obvious solutions based on directly dynamizing solutions to the static version of this problem all require \(\Omega ((\lg n{/}\lg \lg n)^2)\) time for each node reported, and thus our query time is much faster. We also design data structures that support path counting and path reporting queries in \(O((\lg n{/}\lg \lg n)^2)\) time, and insertions and deletions in \(O((\lg n{/}\lg \lg n)^2)\) amortized time. This matches the best known results for dynamic two-dimensional range counting (He and Munro in Comput Geom 47(2):268–281, 2014) and range selection (He et al., in: Proceedings of the 22nd international symposium on algorithms and computation, ISAAC, Yokohama, Japan, 2011), which can be viewed as special cases of path counting and path selection.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0413-x
      Issue No: Vol. 80, No. 12 (2018)
  • Path Refinement in Weighted Regions
    • Authors: Amin Gheibi; Anil Maheshwari; Jörg-Rüdiger Sack; Christian Scheffer
      Pages: 3766 - 3802
      Abstract: In this paper, we study the weighted region problem (WRP) which is to compute a shortest path in a weighted partitioning of a plane. Recent results show that WRP is not solvable in any algebraic computation model over the rational numbers. Therefore, it is unlikely that WRP can be solved in polynomial time. Research has thus focused on determining approximate solutions for WRP. Approximate solutions for WRP typically show qualitatively different behaviors. We first formulate two qualitative criteria for weighted shortest paths. Then, we show how to produce a path that is quantitatively close-to-optimal and qualitatively satisfactory. More precisely, we propose an algorithm to transform any given approximate linear path into a linear path with the same (or shorter) weighted length for which we can prove that it satisfies the required qualitative criteria. This algorithm has a linear time complexity in the size of the given path. At the end, we explain our experiments on some triangular irregular networks (TINs) from Earth’s terrain. The results show that using the proposed algorithm, on average, 51% in query time and 69% in memory usage could be saved, in comparison with the existing method.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0414-9
      Issue No: Vol. 80, No. 12 (2018)
  • Quasimetric Embeddings and Their Applications
    • Authors: Facundo Mémoli; Anastasios Sidiropoulos; Vijay Sridhar
      Pages: 3803 - 3824
      Abstract: We study generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise naturally from the shortest-path distances on directed graphs. Perhaps surprisingly, very little is known about low-distortion embeddings for quasimetric spaces.Random embeddings into ultrametric spaces are arguably one of the most successful geometric tools in the context of algorithm design. We extend this to the quasimetric case as follows. We show that any n-point quasimetric space supported on a graph of treewidth t admits a random embedding into quasiultrametric spaces with distortion \(O(t \log ^2 n)\) , where quasiultrametrics are a natural generalization of ultrametrics. This result allows us to obtain \(t\log ^{O(1)} n\) -approximation algorithms for the Directed Non-Bipartite Sparsest Cut and the Directed Multicut problems on n-vertex graphs of treewidth t, with running time polynomial in both n and t. The above results are obtained by considering a generalization of random partitions to the quasimetric case, which we refer to as random quasipartitions. Using this definition and a construction of Chuzhoy and Khanna (JACM 56(2):6, 2009) we derive a polynomial lower bound on the distortion of random embeddings of general quasimetric spaces into quasiultrametric spaces. Finally, we establish a lower bound for embedding the shortest-path quasimetric of a graph G into graphs that exclude G as a minor. This lower bound is used to show that several embedding results from the metric case do not have natural analogues in the quasimetric setting.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0415-8
      Issue No: Vol. 80, No. 12 (2018)
  • Approximation Schemes for Minimizing the Maximum Lateness on a Single
    • Authors: Imed Kacem; Hans Kellerer
      Pages: 3825 - 3843
      Abstract: In this paper, we consider four single-machine scheduling problems with release times, with the aim of minimizing the maximum lateness. In the first problem we have a common deadline for all the jobs. The second problem looks for the Pareto frontier with respect to the two objective functions maximum lateness and makespan. The third problem is associated with a non-availability constraint. In the fourth one, the non-availability interval is related to the operator who is organizing the execution of jobs on the machine (no job can start, and neither can complete during the operator non-availability period). For each of the four problems, we establish the existence of a polynomial time approximation scheme.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0417-6
      Issue No: Vol. 80, No. 12 (2018)
  • $$(k,n-k)$$ ( k , n - k ) - Max - Cut : An $$\mathcal{O}^*(2^p)$$ O ∗ (
           2 p ) -Time Algorithm and a Polynomial Kernel
    • Authors: Saket Saurabh; Meirav Zehavi
      Pages: 3844 - 3860
      Abstract: Max-Cut is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph \(G=(V,E)\) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if \(p\le E /2\) , the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called \((k,n-k)\) -Max-Cut, restricts the size of the subset A to be exactly k. For the \((k,n-k)\) -Max-Cut problem, we obtain an \(\mathcal{O}^*(2^p)\) -time algorithm, improving upon the previous best \(\mathcal{O}^*(4^{p+o(p)})\) -time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0418-5
      Issue No: Vol. 80, No. 12 (2018)
  • Fast Approximation Algorithms for p -Centers in Large $$\delta $$ δ
           -Hyperbolic Graphs
    • Authors: Katherine Edwards; W. Sean Kennedy; Iraj Saniee
      Pages: 3889 - 3907
      Abstract: We provide a quasilinear time algorithm for the p-center problem with an additive error less than or equal to 3 times the input graph’s hyperbolic constant. Specifically, for the graph \(G=(V,E)\) with n vertices, m edges and hyperbolic constant \(\delta \) , we construct an algorithm for p-centers in time \(O(p(\delta +1)(n+m)\log (n))\) with radius not exceeding \(r_p + \delta \) when \(p \le 2\) and \(r_p + 3\delta \) when \(p \ge 3\) , where \(r_p\) are the optimal radii. Prior work identified p-centers with accuracy \(r_p+\delta \) but with time complexity \(O((n^3\log n + n^2m)\log ({{\mathrm{diam}}}(G)))\) which is impractical for large graphs.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0425-6
      Issue No: Vol. 80, No. 12 (2018)
  • Counting Minimum Weight Arborescences
    • Authors: Koyo Hayashi; Satoru Iwata
      Pages: 3908 - 3919
      Abstract: In a directed graph \(D = (V, A)\) with a specified vertex \(r \in V\) , an arc subset \(B \subseteq A\) is called an r-arborescence if B has no arc entering r and there is a unique path from r to v in (V, B) for each \(v \in V \backslash \{ r \}\) . The problem of finding a minimum weight r-arborescence in a weighted digraph has been studied for decades starting with Chu and Liu (Sci Sin 14:1396–1400, 1965), Edmonds (J Res Natl Bur Stand 71B:233–240, 1967) and Bock (Developments in operations research, Gordon and Breach, New York, pp 29–44, 1971). In this paper, we focus on the number of minimum weight arborescences. We present an algorithm for counting minimum weight r-arborescences in \(O(n^{\omega })\) time, where n is the number of vertices of an input digraph and \(\omega \) is the matrix multiplication exponent.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0426-5
      Issue No: Vol. 80, No. 12 (2018)
  • Lift-and-Project Methods for Set Cover and Knapsack
    • Authors: Eden Chlamtáč; Zachary Friggstad; Konstantinos Georgiou
      Pages: 3920 - 3942
      Abstract: We study the applicability of lift-and-project methods to the Set Cover and Knapsack problems. Inspired by recent work of Karlin et al. (IPCO 2011), who examined this connection for Knapsack, we consider the applicability and limitations of these methods for Set Cover, as well as extend the existing results for Knapsack. For the Set Cover problem, Cygan et al. (IPL 2009) gave sub-exponential-time approximation algorithms with approximation ratios better than \(\ln n\) . We present a very simple combinatorial algorithm which has nearly the same time-approximation tradeoff as the algorithm of Cygan et al. We then adapt this to an LP-based algorithm using the LP hierarchy of Lovász and Schrijver. However, our approach involves the trick of “lifting the objective function”. We show that this trick is essential, by demonstrating an integrality gap of \((1-\varepsilon )\ln n\) at level \(\Omega (n)\) of the stronger LP hierarchy of Sherali and Adams (when the objective function is not lifted). Finally, we show that the SDP hierarchy of Lovász and Schrijver ( \(\mathrm{LS}_+\) ) reduces the integrality gap for Knapsack to \((1+\varepsilon )\) at level O(1). This stands in contrast to Set Cover (where the work of Aleknovich et al. (STOC 2005) rules out any improvement using \(\mathrm{LS}_+\) ), and extends the work of Karlin et al., who demonstrated such an improvement only for the more powerful SDP hierarchy of Lasserre. Our \(\mathrm{LS}_+\) -based rounding and analysis are quite different from theirs (in particular, not relying on the decomposition theorem they prove for the Lasserre hierarchy), and to the best of our knowledge represents the first explicit demonstration of such a reduction in the integrality gap of \(\mathrm{LS}_+\) relaxations after a constant number of rounds.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0427-4
      Issue No: Vol. 80, No. 12 (2018)
  • Extreme Witnesses and Their Applications
    • Authors: Andrzej Lingas; Mia Persson
      Pages: 3943 - 3957
      Abstract: We study the problem of computing the so called minimum and maximum witnesses for Boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for Boolean matrix product. First, we present an \(\tilde{O}(n^{1.5}k^{0.5})\) -time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors, where the notation \(\tilde{O}(\ )\) suppresses polylogarithmic in n factors. In consequence, we obtain new upper time bounds on reporting positions of mismatches in potential string alignments and on computing restricted cases of the \((\min , +)\) vector convolution. Next, we present a fast (substantially subcubic in n and linear in k) algorithm for the smallest or largest k-witness problem for the Boolean matrix product of two \(n\times n\) Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0492-8
      Issue No: Vol. 80, No. 12 (2018)
  • Editor’s Note
    • Pages: 3958 - 3958
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0508-4
      Issue No: Vol. 80, No. 12 (2018)
  • The Fast Search Number of a Complete k -Partite Graph
    • Authors: Yuan Xue; Boting Yang; Farong Zhong; Sandra Zilles
      Pages: 3959 - 3981
      Abstract: Research on graph searching has recently gained interest in computer science, mathematics, and physics. This paper studies fast searching of a fugitive in a graph, a model that was introduced by Dyer et al. (in: Fleischer, Xu (eds.) Algorithmic aspects in information and management, Springer, New York, 2008). We provide lower bounds and upper bounds on the fast search number (i.e., the minimum number of searchers required for capturing the fugitive) of complete k-partite graphs. We also investigate some special classes of complete k-partite graphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs.
      PubDate: 2018-12-01
      DOI: 10.1007/s00453-018-0456-z
      Issue No: Vol. 80, No. 12 (2018)
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-