# zbMATH — the first resource for mathematics

## Information Processing Letters

 Short Title: Inf. Process. Lett. Publisher: Elsevier (North-Holland), Amsterdam ISSN: 0020-0190 Online: http://www.sciencedirect.com/science/journal/00200190 Comments: Indexed cover-to-cover
 Documents Indexed: 7,200 Publications (since 1971) References Indexed: 7,026 Publications with 78,060 References.
all top 5

#### Latest Issues

 173 (2022) 172 (2021) 171 (2021) 170 (2021) 169 (2021) 168 (2021) 167 (2021) 166 (2021) 165 (2021) 164 (2020) 163 (2020) 162 (2020) 161 (2020) 159-160 (2020) 158 (2020) 157 (2020) 156 (2020) 155 (2020) 154 (2020) 153 (2020) 152 (2019) 151 (2019) 150 (2019) 149 (2019) 148 (2019) 147 (2019) 146 (2019) 145 (2019) 144 (2019) 143 (2019) 142 (2019) 141 (2019) 140 (2018) 139 (2018) 138 (2018) 137 (2018) 136 (2018) 135 (2018) 134 (2018) 133 (2018) 132 (2018) 131 (2018) 130 (2018) 129 (2018) 128 (2017) 127 (2017) 126 (2017) 125 (2017) 124 (2017) 123 (2017) 122 (2017) 121 (2017) 120 (2017) 119 (2017) 118 (2017) 117 (2017) 116, No. 12 (2016) 116, No. 11 (2016) 116, No. 10 (2016) 116, No. 9 (2016) 116, No. 8 (2016) 116, No. 7 (2016) 116, No. 6 (2016) 116, No. 5 (2016) 116, No. 4 (2016) 116, No. 3 (2016) 116, No. 2 (2016) 116, No. 1 (2016) 115, No. 12 (2015) 115, No. 11 (2015) 115, No. 10 (2015) 115, No. 9 (2015) 115, No. 6-8 (2015) 115, No. 5 (2015) 115, No. 4 (2015) 115, No. 3 (2015) 115, No. 2 (2015) 115, No. 1 (2015) 114, No. 12 (2014) 114, No. 11 (2014) 114, No. 10 (2014) 114, No. 9 (2014) 114, No. 8 (2014) 114, No. 7 (2014) 114, No. 6 (2014) 114, No. 5 (2014) 114, No. 4 (2014) 114, No. 3 (2014) 114, No. 1-2 (2014) 113, No. 22-24 (2013) 113, No. 19-21 (2013) 113, No. 18 (2013) 113, No. 17 (2013) 113, No. 14-16 (2013) 113, No. 13 (2013) 113, No. 12 (2013) 113, No. 10-11 (2013) 113, No. 9 (2013) 113, No. 8 (2013) 113, No. 7 (2013) ...and 583 more Volumes
all top 5

#### Authors

 27 Rytter, Wojciech 22 Hsu, Lihhsing 22 Woeginger, Gerhard Johannes 21 Lingas, Andrzej 20 Mehlhorn, Kurt 18 Raynal, Michel 18 Xu, Junming 17 Tang, Chuan Yi 17 Tarjan, Robert Endre 17 Wang, Yue-Li 16 Crochemore, Maxime 16 Rangan, Chandrasekharan Pandu 15 Cheng, Tai-Chiu Edwin 15 Rozenberg, Grzegorz 15 Szepietowski, Andrzej 15 Szwarcfiter, Jayme Luiz 14 Choe, Kwang-Moo 14 Leung, Joseph Y.-T. 14 Wegener, Ingo 13 Chang, Jou-Ming 13 Hassin, Refael 13 Luccio, Fabrizio 13 Mäkinen, Erkki 13 Pelc, Andrzej 12 Bollig, Beate 12 Chang, Maw-Shang 12 Chen, Xiebin 12 Chrobak, Marek 12 Meng, Jixiang 12 Rautenbach, Dieter 12 Shallit, Jeffrey O. 12 Xu, Yinfeng 12 Yang, Xiaofan 11 Akl, Selim G. 11 Amir, Amihood 11 Chin, Francis Y. L. 11 Chwa, Kyungyong 11 De Santis, Alfredo 11 Gavril, Fanica 11 Huang, Shingtsaan 11 Iliopoulos, Costas S. 11 Nagamochi, Hiroshi 11 Pagli, Linda 11 Raspaud, André 11 Tan, Xuehou 11 Tsai, Chang-Hsiung 11 Tsur, Dekel 11 Yuan, Jinjiang 10 Bertossi, Alan A. 10 Brandstädt, Andreas 10 Chen, Genhuey 10 Damaschke, Peter 10 Frieze, Alan Michael 10 Gries, David 10 Khuller, Samir 10 Kratsch, Dieter 10 Larmore, Lawrence L. 10 Mosheiov, Gur 10 Nandy, Subhas Chandra 10 Shparlinski, Igor E. 9 Aggarwal, Alok 9 Baeza-Yates, Ricardo A. 9 Chakrabarti, Partha Pratim 9 Chang, Gerard Jennhwa 9 Chen, Jian-er 9 Culik, Karel II 9 de Figueiredo, Celina M. Herrera 9 Ehrenfeucht, Andrzej 9 Engelfriet, Joost 9 Goldreich, Oded 9 Hwang, Tzonelih 9 Ibarra, Oscar H. 9 Inoue, Katsushi 9 Kim, Sung Kwon 9 Landau, Gad M. 9 Lee, Richard Chia-Tung 9 Lin, Min-Sheng 9 Misra, Jayadev 9 Mitchell, Joseph S. B. 9 Overmars, Mark H. 9 Papadimitriou, Christos Harilaos 9 Rahman, Mohammad Sohel 9 Santoro, Nicola 9 Saxena, Sanjeev Kumar 9 Tan, Jimmy J. M. 9 Tsin, Yung Hyang 9 Urrutia Galicia, Jorge L. 9 Wood, Derick 8 Aceto, Luca 8 Allison, Lloyd 8 Atallah, Mikhail J. 8 Bergstra, Jan A. 8 Błażewicz, Jacek 8 Bodlaender, Hans L. 8 Book, Ronald Vernon 8 Chen, Rong-Jaye 8 Chen, Zhizhong 8 de Luca, Aldo 8 Fomin, Fedor V. 8 Fredriksson, Kimmo ...and 8,369 more Authors
all top 5

#### Fields

 6,378 Computer science (68-XX) 1,275 Combinatorics (05-XX) 548 Information and communication theory, circuits (94-XX) 398 Operations research, mathematical programming (90-XX) 287 Mathematical logic and foundations (03-XX) 153 Numerical analysis (65-XX) 119 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 104 Number theory (11-XX) 88 Convex and discrete geometry (52-XX) 42 Order, lattices, ordered algebraic structures (06-XX) 41 Biology and other natural sciences (92-XX) 30 Linear and multilinear algebra; matrix theory (15-XX) 28 Probability theory and stochastic processes (60-XX) 26 Group theory and generalizations (20-XX) 24 Statistics (62-XX) 21 Quantum theory (81-XX) 16 Systems theory; control (93-XX) 9 Field theory and polynomials (12-XX) 9 Algebraic geometry (14-XX) 9 Geometry (51-XX) 6 General and overarching topics; collections (00-XX) 6 General algebraic systems (08-XX) 6 Real functions (26-XX) 5 Measure and integration (28-XX) 4 History and biography (01-XX) 4 Commutative algebra (13-XX) 4 Category theory; homological algebra (18-XX) 4 Ordinary differential equations (34-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Approximations and expansions (41-XX) 3 Associative rings and algebras (16-XX) 3 Functions of a complex variable (30-XX) 3 Special functions (33-XX) 3 General topology (54-XX) 2 Partial differential equations (35-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 Nonassociative rings and algebras (17-XX) 1 Topological groups, Lie groups (22-XX) 1 Difference and functional equations (39-XX) 1 Sequences, series, summability (40-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Integral transforms, operational calculus (44-XX) 1 Functional analysis (46-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Mechanics of particles and systems (70-XX) 1 Mechanics of deformable solids (74-XX) 1 Fluid mechanics (76-XX) 1 Classical thermodynamics, heat transfer (80-XX)

#### Citations contained in zbMATH Open

4,907 Publications have been cited 31,084 times in 21,632 Documents Cited by Year
A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Zbl 0398.68042
Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert Endre
1979
An efficient algorithm for determining the convex hull of a finite planar set. Zbl 0236.68013
Graham, R. L.
1972
On generating all maximal independent sets. Zbl 0654.68086
Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H.
1988
On computing a conditional edge-connectivity of a graph. Zbl 0633.05045
Esfahanian, Abdol-Hossein; Hakimi, S. Louis
1988
Optimal packing and covering in the plane are NP-complete. Zbl 0469.68053
Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L.
1981
Occam’s razor. Zbl 0653.68084
Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K.
1987
Fixed-parameter tractability of graph modification problems for hereditary properties. Zbl 0875.68702
Cai, Leizhen
1996
The particle swarm optimization algorithm: Convergence analysis and parameter selection. Zbl 1156.90463
Trelea, Ioan Cristian
2003
A calculus of durations. Zbl 0743.68097
Zhou, Chaochen; Hoare, C. A. R.; Ravn, Anders P.
1991
Preserving order in a forest in less than logarithmic time and linear space. Zbl 0364.68053
van Emde Boas, P.
1977
On computing the determinant in small parallel time using a small number of processors. Zbl 0541.68019
Berkowitz, Stuart J.
1984
Defining liveness. Zbl 0575.68030
Alpern, Bowen; Schneider, Fred B.
1985
Finding the upper envelope of n line segments in O(n log n) time. Zbl 0689.68058
Hershberger, John
1989
A guided tour of Chernoff bounds. Zbl 0702.60021
Hagerup, Torben; Rüb, Christine
1990
An optimal algorithm for computing the repetitions in a word. Zbl 0467.68075
Crochemore, Max
1981
A linear algorithm for the domination number of a tree. Zbl 0311.68024
Cockayne, E.; Goodman, S.; Hedetniemi, S.
1975
Relative complexity of checking and evaluating. Zbl 0342.68028
Valiant, Leslie G.
1976
A probabilistic remark on algebraic program testing. Zbl 0397.68011
DeMillo, Richard A.; Lipton, Richard J.
1978
A $$max \{m, n \}$$ algorithm for determining the graph H from its line graph G. Zbl 0274.05116
Roussopoulos, Nicholas D.
1973
NP-completeness of some generalizations of the maximum matching problem. Zbl 0493.68039
Stockmeyer, Larry J.; Vazirani, Vijay V.
1982
Maximum bounded 3-dimensional matching is MAX SNP-complete. Zbl 0711.68045
Kann, Viggo
1991
On the identification of the convex hull of a finite set of points in the plane. Zbl 0256.68041
Jarvis, R. A.
1973
Application of a stochastic name-passing calculus to representation and simulation of molecular processes. Zbl 0997.92018
Priami, Corrado; Regev, Aviv; Shapiro, Ehud; Silverman, William
2001
Intersection and union of regular languages and state complexity. Zbl 0763.68048
Birget, Jean-Camille
1992
Does co-NP have short interactive proofs ? Zbl 0653.68037
Boppana, Ravi B.; Håstad, Johan; Zachos, Stathis
1987
The vertex separation number of a graph equals its path-width. Zbl 0764.68121
Kinnersley, Nancy G.
1992
Dominating sets for split and bipartite graphs. Zbl 0539.68058
Bertossi, Alan A.
1984
Log-logarithmic worst-case range queries are possible in space theta(N). Zbl 0509.68106
Willard, Dan E.
1983
Constructing optimal binary decision trees is NP-complete. Zbl 0333.68029
Hyafil, Laurent; Rivest, Ronald L.
1976
The Steiner problem with edge lengths 1 and 2. Zbl 0677.68074
Bern, Marshall; Plassmann, Paul
1989
The budgeted maximum coverage problem. Zbl 1002.68203
Khuller, Samir; Moss, Anna; Naor, Joseph
1999
An improved lower bound for on-line bin packing algorithms. Zbl 0764.68083
van Vliet, André
1992
A lower bound for the time to assure interactive consistency. Zbl 0493.68026
Fischer, Michael J.; Lynch, Nancy A.
1982
Arrangement graphs: A class of generalized star graphs. Zbl 0772.68005
Day, Khaled; Tripathi, Anand
1992
Voronoi diagrams from convex hulls. Zbl 0424.68036
Brown, Kevin Q.
1979
Myths about the mutual exclusion problem. Zbl 0474.68031
Peterson, G. L.
1981
Good and semi-strong colorings of oriented planar graphs. Zbl 0806.05031
Raspaud, André; Sopena, Eric
1994
Paw-free graphs. Zbl 0654.05063
Olariu, Stephan
1988
Deciding the winner in parity games is in $$\mathrm{UP}\cap\mathrm{co-UP}$$. Zbl 1338.68109
Jurdziński, Marcin
1998
Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes. Zbl 1161.68684
Li, Tseng-Kuei; Tsai, Chang-Hsiung; Tan, Jimmy J. M.; Hsu, Lih-Hsing
2003
Simple linear time recognition of unit interval graphs. Zbl 0875.68690
Corneil, Derek G.; Kim, Hiryoung; Natarajan, Sridhar; Olariu, Stephan; Sprague, Alan P.
1995
A Kolmogorov complexity characterization of constructive Hausdorff dimension. Zbl 1045.68570
Mayordomo, Elvira
2002
Finding Hamiltonian circuits in interval graphs. Zbl 0578.68053
Keil, J. Mark
1985
Optimal speedup of Las Vegas algorithms. Zbl 0797.68139
Luby, Michael; Sinclair, Alistair; Zuckerman, David
1993
A lower bound technique for the size of nondeterministic finite automata. Zbl 0900.68313
Glaister, Ian; Shallit, Jeffrey
1996
Minimizing the sum of the $$k$$ largest functions in linear time. Zbl 1050.68155
Ogryczak, Wlodzimierz; Tamir, Arie
2003
Finding paths of length $$k$$ in $$O^{*}(2^k)$$ time. Zbl 1191.68857
Williams, Ryan
2009
Triangulating a simple polygon. Zbl 0384.68040
Garey, Michael R.; Johnson, David S.; Preparata, Franco P.; Tarjan, Robert E.
1978
An $$O(IVI^3)$$ algorithm for finding maximum flows in networks. Zbl 0391.90041
Malhotra, V. M.; Kumar, M. Pramodh; Maheshwari, S. N.
1978
An algorithm for drawing general undirected graphs. Zbl 0679.68128
1989
A unified approach to domination problems on interval graphs. Zbl 0658.05040
Ramalingam, G.; Pandu Rangan, C.
1988
On the limits of efficient teachability. Zbl 1032.68662
Servedio, R. A.
2001
The $$(n,k)$$-star graph: A generalized star graph. Zbl 1027.68645
Chiang, Wei-Kuo; Chen, Rong-Jaye
1995
Acyclic colorings of subcubic graphs. Zbl 1169.05325
Skulrattanakulchai, San
2004
The maximum k-colorable subgraph problem for chordal graphs. Zbl 0653.68070
Yannakakis, Mihalis; Gavril, Fanica
1987
A note on the complexity of the chromatic number problem. Zbl 0336.68021
Lawler, E. L.
1976
An algorithm for finding clique cut-sets. Zbl 0454.68078
Whitesides, S. H.
1981
Complexity of scheduling tasks with time-dependent execution times. Zbl 0942.68508
Ho, Kevin I-J.; Leung, Joseph Y-T.; Wei, W-D.
1993
$$0(n^{2.7799})$$ complexity for $$n\times n$$ approximate matrix multiplication. Zbl 0395.68048
Bini, Dario; Capovani, Milvio; Romani, Francesco; Lotti, Grazia
1979
Decomposable searching problems. Zbl 0404.68067
Bentley, Jon Louis
1979
Counterexamples to termination for the direct sum of term rewriting systems. Zbl 0653.68010
Toyama, Yoshihito
1987
BPP and the polynomial hierarchy. Zbl 0515.68042
Lautemann, Clemens
1983
Linear algorithm for optimal path cover problem on interval graphs. Zbl 0697.68048
Rao Arikati, Srinivasa; Pandu Rangan, C.
1990
An approximation algorithm for interval data minmax regret combinatorial optimization problems. Zbl 1184.68640
2006
$$k$$-tuple domination in graphs. Zbl 1175.68299
Liao, Chung-Shou; Chang, Gerard J.
2003
A note on the graph isomorphism counting problem. Zbl 0395.68057
Mathon, Rudolf
1979
Doubly lexical ordering of dense 0–1 matrices. Zbl 0771.68068
1993
Constructing the visibility graph for n-line segments in $$O(n^ 2)$$ time. Zbl 0573.68036
Welzl, Emo
1985
The minimum labeling spanning trees. Zbl 0938.90063
Chang, Ruay-Shiung; Leu, Shing-Jiuan
1997
On the minimum label spanning tree problem. Zbl 0938.90064
Krumke, Sven; Wirth, Hans-Christoph
1998
Pattern matching for permutations. Zbl 1338.68304
Bose, Prosenjit; Buss, Jonathan F.; Lubiw, Anna
1998
A faster approximation algorithm for the Steiner problem in graphs. Zbl 0635.68071
Mehlhorn, Kurt
1988
Termination detection for diffusing computations. Zbl 0439.68039
Dijkstra, Edsger W.; Scholten, C. S.
1980
Fault-tolerant Hamiltonian laceability of hypercubes. Zbl 1043.68081
Tsai, Chang-Hsiung; Tan, Jimmy J. M.; Liang, Tyne; Hsu, Lih-Hsing
2002
Private vs. common random bits in communication complexity. Zbl 0735.68034
Newman, Ilan
1991
Finding good approximate vertex and edge partitions is NP-hard. Zbl 0764.68061
Bui, Thang Nguyen; Jones, Curt
1992
Divide and conquer for linear expected time. Zbl 0404.68046
Bentley, Jon Louis; Shamos, Michael Ian
1978
Minimizing the total weighted completion time of deteriorating jobs. Zbl 1032.68019
Bachman, Aleksander; Janiak, Adam; Kovalyov, Mikhail Y.
2002
On maximum induced matchings in bipartite graphs. Zbl 1046.68081
Lozin, V. V.
2002
Conditional connectivity of Cayley graphs generated by transposition trees. Zbl 1379.05069
Yang, Weihua; Li, Hengzhe; Meng, Jixiang
2010
An optimal greedy heuristic to color interval graphs. Zbl 0711.68083
Olariu, Stephan
1991
An on-line string superprimitivity test. Zbl 0795.68079
Breslauer, Dany
1992
Some characterizations of Parikh matrix equivalent binary words. Zbl 1173.68550
Fossé, S.; Richomme, G.
2004
The Min-Max Spanning Tree Problem and some extensions. Zbl 0373.05028
Camerini, P. M.
1978
A 3-approximation algorithm for the $$k$$-level uncapacitated facility location problem. Zbl 0994.90090
Aardal, Karen; Chudak, Fabián A.; Shmoys, David B.
1999
A note on scheduling on a single processor with speed dependent on a number of executed jobs. Zbl 0875.68080
Gawiejnowicz, Stanisław
1996
Parallel computation and conflicts in memory access. Zbl 0498.68029
Kucera, Ludek
1982
Connectivity and edge-disjoint spanning trees. Zbl 0507.05030
Gusfield, Dan
1983
The constrained longest common subsequence problem. Zbl 1175.90407
Tsai, Yin-Te
2003
A general method to speed up fixed-parameter-tractable algorithms. Zbl 1014.68064
Niedermeier, Rolf; Rossmanith, Peter
2000
Domination in convex and chordal bipartite graphs. Zbl 0706.68055
Damaschke, Peter; Müller, Haiko; Kratsch, Dieter
1990
Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Zbl 1205.68516
Lee, Kangbok; Choi, Byung-Cheon; Leung, Joseph Y.-T.; Pinedo, Michael L.
2009
Optimal node ranking of trees. Zbl 0661.68063
Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, G.
1988
An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Zbl 0555.90069
Zemel, Eitan
1984
A lower bound for on-line bin packing. Zbl 0444.68061
Liang, Frank M.
1980
The edge Hamiltonian path problem is NP-complete. Zbl 0495.68058
Bertossi, Alan A.
1981
Some results on graphs without long induced paths. Zbl 1178.68285
2003
The complexity of scheduling starting time dependent tasks with release times. Zbl 1338.68096
Cheng, T. C. E.; Ding, Q.
1998
Computing a maximum cardinality matching in a bipartite graph in time $$O(n^{1,5}\sqrt{m/\log \,n})$$. Zbl 0714.68036
Alt, H.; Blum, N.; Mehlhorn, K.; Paul, M.
1991
Alphabet dependence in parameterized matching. Zbl 0795.68077
Amir, Amihood; Farach, Martin; Muthukrishnan, S.
1994
A queueing network-based distributed Laplacian solver for directed graphs. Zbl 07306062
Gillani, Iqra Altaf; Bagchi, Amitabha
2021
Catalan and Schröder permutations sortable by two restricted stacks. Zbl 07360091
Baril, Jean-Luc; Cerbai, Giulio; Khalil, Carine; Vajnovszki, Vincent
2021
Robbins and Ardila meet Berstel. Zbl 07319590
Shallit, Jeffrey
2021
Testing gap $$k$$-planarity is NP-complete. Zbl 07360066
Urschel, John C.; Wellens, Jake
2021
An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time. Zbl 07138141
Dragan, Feodor F.
2020
Signed coloring of 2-dimensional grids. Zbl 07165913
Dybizbański, Janusz; Nenca, Anna; Szepietowski, Andrzej
2020
Effective definability of the reachability relation in timed automata. Zbl 07134468
Fränzle, Martin; Quaas, Karin; Shirmohammadi, Mahsa; Worrell, James
2020
Some reduction operations to pairwise compatibility graphs. Zbl 07134470
Xiao, Mingyu; Nagamochi, Hiroshi
2020
Modified quadratic residue constructions and new extremal binary self-dual codes of lengths 64, 66 and 68. Zbl 07168547
Gildea, Joe; Hamilton, Holly; Kaya, Abidin; Yildiz, Bahattin
2020
Faster algorithms for cograph edge modification problems. Zbl 1432.68371
Tsur, Dekel
2020
Raiders of the lost equivalence: probabilistic branching bisimilarity. Zbl 1441.68145
Castiglioni, Valentina; Tini, Simone
2020
Remark on subcodes of linear complementary dual codes. Zbl 07227693
2020
Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs. Zbl 07134466
Biniaz, Ahmad; Maheshwari, Anil; Smid, Michiel
2020
A generic construction of CCA-secure deterministic encryption. Zbl 1468.94401
Huang, Meijuan; Yang, Bo; Zhao, Yi; Wang, Xin; Zhou, Yanwei; Xia, Zhe
2020
Graphs without a partition into two proportionally dense subgraphs. Zbl 07145937
Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément
2020
A subset-sum type formulation of a two-agent single-machine scheduling problem. Zbl 07145938
Avolio, Matteo; Fuduli, Antonio
2020
On the computational complexity of length- and neighborhood-constrained path problems. Zbl 07165910
Luckow, Max-Jonathan; Fluschnik, Till
2020
Recognizing and realizing cactus metrics. Zbl 1447.05186
Hayamizu, Momoko; Huber, Katharina T.; Moulton, Vincent; Murakami, Yukihiro
2020
Maximum-area triangle in a convex polygon, revisited. Zbl 1441.68272
van der Hoog, Ivor; Keikha, Vahideh; Löffler, Maarten; Mohades, Ali; Urhausen, Jérôme
2020
On the complexity of detecting hazards. Zbl 1462.68072
Komarath, Balagopal; Saurabh, Nitin
2020
Lengths of words accepted by nondeterministic finite automata. Zbl 1461.68104
Potechin, Aaron; Shallit, Jeffrey
2020
Lot scheduling on a single machine to minimize the (weighted) number of tardy orders. Zbl 1466.90035
Mor, Baruch; Mosheiov, Gur; Shapira, Dana
2020
Degree conditions for fractional $$(a,b,k)$$-critical covered graphs. Zbl 07115185
Zhou, Sizhong; Xu, Yang; Sun, Zhiren
2019
Improving the diameters of completely independent spanning trees in locally twisted cubes. Zbl 06975553
Pai, Kung-Jui; Chang, Jou-Ming
2019
Thorup-Zwick emulators are universally optimal hopsets. Zbl 1470.68059
Huang, Shang-En; Pettie, Seth
2019
Single machine lot scheduling to minimize the total weighted (discounted) completion time. Zbl 1469.90078
Zhang, E.; Liu, Ming; Zheng, Feifeng; Xu, Yinfeng
2019
The secure domination problem in cographs. Zbl 1451.05177
Jha, Anupriya; Pradhan, Dina; Banerjee, Sumanta
2019
A new lower bound on the price of anarchy of selfish bin packing. Zbl 1460.91052
Dósa, György; Epstein, Leah
2019
Greedy can beat pure dynamic programming. Zbl 1469.68168
Jukna, Stasys; Seiwert, Hannes
2019
A degree condition for fractional $$[a,b]$$-covered graphs. Zbl 07003079
Yuan, Yuan; Hao, Rong-Xia
2019
A note on the efficiency of position mechanisms with budget constraints. Zbl 07003081
Voudouris, Alexandros A.
2019
New lower bound on the Shannon capacity of $$C_7$$ from circular graphs. Zbl 07003083
Polak, Sven C.; Schrijver, Alexander
2019
On error linear complexity of new generalized cyclotomic binary sequences of period $$p^2$$. Zbl 07021525
Wu, Chenhuang; Xu, Chunxiang; Chen, Zhixiong; Ke, Pinhui
2019
Edge-disjoint Hamiltonian cycles of balanced hypercubes. Zbl 07021527
Lü, Huazhong; Wu, Tingzeng
2019
Paths between colourings of graphs with bounded tree-width. Zbl 1405.05059
Feghali, Carl
2019
Fault-tolerant-prescribed Hamiltonian laceability of balanced hypercubes. Zbl 1446.68128
Yang, Yuxing; Zhang, Lingling
2019
Comments on “Proportionate flowshops with general position dependent processing times” and “Minimizing total load on a proportionate flowshop with position-dependent processing times and job-rejection”. Zbl 1411.90149
Kovalyov, Mikhail Y.; Mosheiov, Gur; Šešok, Dmitrij
2019
Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform. Zbl 07053454
Daykin, J. W.; Groult, R.; Guesnet, Y.; Lecroq, Thierry; Lefebvre, A.; Léonard, M.; Mouchard, L.; Prieur-Gaston, É.; Watson, B.
2019
Improved Zhang neural network with finite-time convergence for time-varying linear system of equations solving. Zbl 07053455
Lv, Xuanjiao; Xiao, Lin; Tan, Zhiguo
2019
An observation on NORX, BLAKE2, and ChaCha. Zbl 1458.94273
Neves, Samuel; Araujo, Filipe
2019
A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries. Zbl 07107762
Surinx, Dimitri; Van den Bussche, Jan
2019
Crash-tolerant causal broadcast in $$O(n)$$ messages. Zbl 1461.94109
Mostéfaoui, Achour; Perrin, Matthieu; Raynal, Michel; Cao, Jiannong
2019
$$\mathsf{NP}$$-hardness of geometric set cover and hitting set with rectangles containing a common point. Zbl 06975550
2019
Nonlinear gradient neural network for solving system of linear equations. Zbl 1469.68012
Xiao, Lin; Li, Kenli; Tan, Zhiguo; Zhang, Zhijun; Liao, Bolin; Chen, Ke; Jin, Long; Li, Shuai
2019
The super connectivity of folded crossed cubes. Zbl 1469.68074
Cai, Xuepeng; Vumar, Elkin
2019
A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph. Zbl 1469.68076
Park, Jung-Heum; Ihm, Insung
2019
A note on domination 3-edge-critical planar graphs. Zbl 06989090
Furuya, Michitaka; Matsumoto, Naoki
2019
On exploring always-connected temporal graphs of small pathwidth. Zbl 1469.68072
Bodlaender, Hans L.; van der Zanden, Tom C.
2019
On the conjecture of vertex-transitivity of DCell. Zbl 1470.68063
Lü, Huazhong
2019
On the parameterized complexity of $$(k,s)$$-SAT. Zbl 07003082
Paulusma, Daniël; Szeider, Stefan
2019
Minimizing the solid angle sum of orthogonal polyhedra. Zbl 07003085
Aldana-Galván, I.; Álvarez-Rebollar, J. L.; Catana-Salazar, J. C.; Jiménez-Salinas, M.; Solís-Villarreal, E.; Urrutia, J.
2019
On the geodetic number of complementary prisms. Zbl 07021530
Castonguay, Diane; Coelho, Erika M. M.; Coelho, Hebert; Nascimento, Julliano R.
2019
Minimum-width annulus with outliers: circular, square, and rectangular cases. Zbl 1446.68172
Ahn, Hee-Kap; Ahn, Taehoon; Bae, Sang Won; Choi, Jongmin; Kim, Mincheol; Oh, Eunjin; Shin, Chan-Su; Yoon, Sang Duk
2019
On shuffle products, acyclic automata and piecewise-testable languages. Zbl 1446.68081
Halfon, S.; Schnoebelen, Ph.
2019
The diagnosability and 1-good-neighbor conditional diagnosability of hypercubes with missing links and broken-down nodes. Zbl 07047942
Li, Xiaoyan; Teng, Yuan-Hsiang; Kung, Tzu-Liang; Chen, Qi; Lin, Cheng-Kuan
2019
The eternal dominating set problem for interval graphs. Zbl 07047943
Rinemberg, Martín; Soulignac, Francisco J.
2019
Security analysis of SIMECK block cipher against related-key impossible differential. Zbl 07053442
2019
Size-optimal top dag compression. Zbl 07053444
Lohrey, Markus; Reh, Carl Philipp; Sieber, Kurt
2019
A new matrix form to generate all $$3\times 3$$ involutory MDS matrices over $$\mathbb{F}_{2^m}$$. Zbl 07053450
Güzel, Gülsüm Gözde; Sakallı, Muharrem Tolga; Akleylek, Sedat; Rijmen, Vincent; Çengellenmiş, Yasemin
2019
A scalable model for building context-aware applications for noncommunicable diseases prevention. Zbl 07062277
Vianna, Henrique Damasceno; Barbosa, Jorge Luis Victória
2019
Double Roman domination in trees. Zbl 06855752
Zhang, Xiujun; Li, Zepeng; Jiang, Huiqin; Shao, Zehui
2018
Minimizing total load on a proportionate flowshop with position-dependent processing times and job-rejection. Zbl 1410.90086
Fiszman, Shir; Mosheiov, Gur
2018
Independent feedback vertex sets for graphs of bounded diameter. Zbl 1422.68104
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
2018
Some results on the inverse sum indeg index of a graph. Zbl 06855754
An, Mingqiang; Xiong, Liming
2018
Leakage-resilient CCA2-secure certificateless public-key encryption scheme without bilinear pairing. Zbl 1422.94034
Zhou, Yanwei; Yang, Bo
2018
Extremal problems on weak Roman domination number. Zbl 1391.05197
Zhu, Enqiang; Shao, Zehui
2018
On colouring $$(2P_2,H)$$-free and $$(P_5,H)$$-free graphs. Zbl 06855753
2018
The pessimistic diagnosability of data center networks. Zbl 06855756
Gu, Mei-Mei; Hao, Rong-Xia; Liu, Jian-Bing
2018
A hardness result and new algorithm for the longest common palindromic subsequence problem. Zbl 1420.68246
Inenaga, Shunsuke; Hyyrö, Heikki
2018
On the hardness of finding the geodetic number of a subcubic graph. Zbl 06856063
Bueno, Letícia R.; Penso, Lucia D.; Protti, Fábio; Ramos, Victor R.; Rautenbach, Dieter; Souza, Uéverton S.
2018
Use of logical models for proving infeasibility in term rewriting. Zbl 06873295
2018
Line segment covering of cells in arrangements. Zbl 1419.68199
Korman, Matias; Poon, Sheung-Hung; Roeloffzen, Marcel
2018
Deterministic improved round-trip spanners. Zbl 1420.68160
Zhu, Chun Jiang; Lam, Kam-Yiu
2018
Inefficiencies in network models: a graph-theoretic perspective. Zbl 1425.90021
Cenciarelli, Pietro; Gorla, Daniele; Salvo, Ivano
2018
On fan-crossing and fan-crossing free graphs. Zbl 1458.68139
Brandenburg, Franz J.
2018
Long directed $$(s,t)$$-path: FPT algorithm. Zbl 06958568
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav
2018
Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement. Zbl 1427.68334
Eder, Günther; Held, Martin
2018
A generalization of orthogonal factorizations in digraphs. Zbl 1429.05171
Sun, Zhiren; Zhou, Sizhong
2018
Enumerating maximal cliques in link streams with durations. Zbl 1426.68227
Viard, Tiphaine; Magnien, Clémence; Latapy, Matthieu
2018
An improved upper bound of edge-vertex domination number of a tree. Zbl 06855749
Venkatakrishnan, Y. B.; Krishnakumari, B.
2018
Linkage on the infinite grid. Zbl 06889959
Jobson, Adam S.; Kézdy, André E.; Lehel, Jenő
2018
NP-completeness of local colorings of graphs. Zbl 1419.68055
Li, Zepeng; Zhu, Enqiang; Shao, Zehui; Xu, Jin
2018
A note on monotone real circuits. Zbl 1422.68115
Hrubeš, Pavel; Pudlák, Pavel
2018
Revisiting AES related-key differential attacks with constraint programming. Zbl 06958539
Gérault, David; Lafourcade, Pascal; Minier, Marine; Solnon, Christine
2018
Fooling sets and the spanning tree polytope. Zbl 1434.90171
Khoshkhah, Kaveh; Theis, Dirk Oliver
2018
A short note on the complexity of computing strong pathbreadth. Zbl 1427.68237
Ducoffe, Guillaume
2018
General parametric scheme for the online uniform machine scheduling problem with two different speeds. Zbl 06855750
Dolgui, Alexandre; Kotov, Vladimir; Nekrashevich, Aliaksandr; Quilliot, Alain
2018
Unifying theories of time with generalised reactive processes. Zbl 06856068
Foster, Simon; Cavalcanti, Ana; Woodcock, Jim; Zeyda, Frank
2018
Approximation algorithms for color spanning diameter. Zbl 06856069
2018
Periodicity of identifying codes in strips. Zbl 06856074
Jiang, Minghui
2018
An improved FPT algorithm for almost forest deletion problem. Zbl 1457.68220
Lin, Mugang; Feng, Qilong; Wang, Jianxin; Chen, Jianer; Fu, Bin; Li, Wenjun
2018
The number of spanning trees of a class of self-similar fractal models. Zbl 06873290
Ma, Fei; Yao, Bing
2018
Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2). Zbl 06889951
Visconti, Andrea; Schiavo, Chiara Valentina; Peralta, René
2018
Notes on complexity of packing coloring. Zbl 06889952
Kim, Minki; Lidický, Bernard; Masařík, Tomáš; Pfender, Florian
2018
On the validity of encodings of the synchronous in the asynchronous $$\pi$$-calculus. Zbl 1390.68490
van Glabbeek, Rob J.
2018
Algorithms for anti-powers in strings. Zbl 1398.68699
Badkobeh, Golnaz; Fici, Gabriele; Puglisi, Simon J.
2018
Translation and scale invariants of Krawtchouk moments. Zbl 1419.68206
Zhi, Ruicong; Cao, Lianyu; Cao, Gang
2018
On maximum leaf trees and connections to connected maximum cut problems. Zbl 1420.68158
Gandhi, Rajiv; Hajiaghayi, Mohammad Taghi; Kortsarz, Guy; Purohit, Manish; Sarpatwar, Kanthi
2018
Feature weighting as a tool for unsupervised feature selection. Zbl 1419.68080
Panday, Deepak; Cordeiro de Amorim, Renato; Lane, Peter
2018
Strong chromatic index of $$K_4$$-minor free graphs. Zbl 1420.05063
Wang, Yiqiao; Wang, Ping; Wang, Weifan
2018
...and 1105 more Documents
all top 5

#### Cited by 21,705 Authors

 71 Saurabh, Saket 61 Cheng, Tai-Chiu Edwin 57 Hsu, Lihhsing 57 Rytter, Wojciech 56 Epstein, Leah 56 Kratsch, Dieter 55 Xu, Junming 53 Wang, Shiying 52 Liotta, Giuseppe 51 Chang, Jou-Ming 51 Fomin, Fedor V. 50 Brandstädt, Andreas 50 Cheng, Eddie 50 Iliopoulos, Costas S. 50 Paulusma, Daniël 49 Golovach, Petr A. 48 Lozin, Vadim Vladislavovich 48 Szwarcfiter, Jayme Luiz 46 Fernau, Henning 46 Heggernes, Pinar 46 Lingas, Andrzej 46 Niedermeier, Rolf 45 Crochemore, Maxime 45 Paschos, Vangelis Th. 45 Rautenbach, Dieter 44 Hemaspaandra, Lane A. 44 Zhang, Zhao 43 Sharir, Micha 43 Woeginger, Gerhard Johannes 42 Chen, Jian-er 42 Raman, Venkatesh 41 Mitchell, Joseph S. B. 41 Pan, Victor Yakovlevich 41 Wang, Yue-Li 40 Chang, Gerard Jennhwa 40 de Figueiredo, Celina M. Herrera 40 Monnot, Jérôme 40 Nagamochi, Hiroshi 40 Wang, Jianxin 39 Hurtado, Ferran 38 Bose, Prosenjit K. 38 Milanič, Martin 38 Yuan, Jinjiang 37 Amir, Amihood 37 Hao, Rongxia 37 Xu, Yinfeng 37 Yang, Xiaofan 37 Zehavi, Meirav 36 Xu, Dachuan 35 Lokshtanov, Daniel 35 Salomaa, Kai T. 35 Tan, Jimmy J. M. 34 Boros, Endre 34 Gutin, Gregory Z. 34 Hsieh, Sun-Yuan 34 Levin, Asaf 34 Navarro, Gonzalo 33 Makino, Kazuhisa 33 Meng, Jixiang 33 Porat, Ely 32 Fan, Jianxi 32 Hromkovič, Juraj 32 Overmars, Mark H. 32 Pelc, Andrzej 32 Yang, Weihua 31 Chan, Timothy Moon-Yew 31 Klavžar, Sandi 31 Lê Văn Băng 31 Mosca, Raffaele 31 Radoszewski, Jakub 31 Xu, Min 30 Alon, Noga M. 30 Błażewicz, Jacek 30 Chandran, L. Sunil 30 Chen, Danny Ziyi 30 Hassin, Refael 30 Rozenberg, Grzegorz 29 Eppstein, David Arthur 29 Inoue, Katsushi 29 Raynal, Michel 29 Toussaint, Godfried T. 28 Chen, Genhuey 28 Holzer, Markus 28 Jansen, Klaus 28 Komusiewicz, Christian 28 Pal, Madhumangal 28 Panda, Bhawani Sankar 28 Tóth, Csaba D. 28 Wu, Jian-Liang 28 Zhou, Shuming 27 Bae, Sang Won 27 Bodlaender, Hans L. 27 Chen, Zhizhong 27 Edelsbrunner, Herbert 27 Fellows, Michael Ralph 27 Guo, Jiong 27 Korman, Matias 27 Kutrib, Martin 27 Lin, Cheng-Kuan 27 Meijer, Henk G. ...and 21,605 more Authors
all top 5

#### Cited in 675 Journals

 2,740 Theoretical Computer Science 2,466 Information Processing Letters 1,446 Discrete Applied Mathematics 762 Algorithmica 553 Journal of Computer and System Sciences 529 Discrete Mathematics 448 Information and Computation 382 Journal of Combinatorial Optimization 372 European Journal of Operational Research 346 Information Sciences 325 Computational Geometry 320 International Journal of Foundations of Computer Science 249 Theory of Computing Systems 246 International Journal of Computer Mathematics 239 Applied Mathematics and Computation 231 Journal of Discrete Algorithms 223 Computers & Operations Research 198 Acta Informatica 187 Distributed Computing 161 Discrete & Computational Geometry 149 Operations Research Letters 141 Graphs and Combinatorics 138 International Journal of Computational Geometry & Applications 129 Annals of Operations Research 122 Computers & Mathematics with Applications 120 SIAM Journal on Computing 112 Artificial Intelligence 106 Mathematical Programming. Series A. Series B 100 Networks 99 Journal of Scheduling 98 SIAM Journal on Discrete Mathematics 92 European Journal of Combinatorics 91 Annals of Mathematics and Artificial Intelligence 90 Discrete Mathematics, Algorithms and Applications 89 Computational Complexity 88 Discrete Optimization 86 Journal of Symbolic Computation 82 Formal Aspects of Computing 80 Optimization Letters 77 BIT 73 Linear Algebra and its Applications 72 Designs, Codes and Cryptography 69 Mathematical Systems Theory 69 RAIRO. Informatique Théorique et Applications 64 Computing 64 RAIRO. Theoretical Informatics and Applications 63 Pattern Recognition 62 Algorithms 60 Mathematical Problems in Engineering 57 Journal of Global Optimization 56 Journal of Graph Theory 54 Journal of Parallel and Distributed Computing 51 Annals of Pure and Applied Logic 50 Journal of Complexity 49 Discussiones Mathematicae. Graph Theory 48 Journal of Combinatorial Theory. Series B 48 Asia-Pacific Journal of Operational Research 48 Real-Time Systems 47 Applied Mathematics Letters 47 Journal of Cryptology 46 Logical Methods in Computer Science 45 Combinatorica 45 Random Structures & Algorithms 45 Applied Mathematical Modelling 44 Journal of Computational and Applied Mathematics 44 Journal of Automated Reasoning 44 RAIRO. Operations Research 43 Parallel Algorithms and Applications 42 Formal Methods in System Design 40 Journal of Combinatorial Theory. Series A 40 The Journal of Logic and Algebraic Programming 40 Journal of Logical and Algebraic Methods in Programming 38 RAIRO, Informatique Théorique 38 MSCS. Mathematical Structures in Computer Science 37 Mathematical and Computer Modelling 36 Journal of Graph Algorithms and Applications 35 Cybernetics and Systems Analysis 35 Quantum Information Processing 34 Computer Science Review 32 Mathematics of Computation 31 Advances in Applied Mathematics 31 Journal of Computer Science and Technology 30 Acta Mathematicae Applicatae Sinica. English Series 29 Automatica 29 Combinatorics, Probability and Computing 29 Mathematics in Computer Science 29 RAIRO. Theoretical Informatics and Applications 28 Order 28 Machine Learning 28 International Transactions in Operational Research 28 4OR 26 International Journal of Systems Science 26 Soft Computing 26 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 26 Cryptography and Communications 25 International Journal of Approximate Reasoning 25 AKCE International Journal of Graphs and Combinatorics 24 Fuzzy Sets and Systems 24 Journal of Information & Optimization Sciences 24 Neural Computation ...and 575 more Journals
all top 5

#### Cited in 60 Fields

 14,484 Computer science (68-XX) 6,246 Combinatorics (05-XX) 3,846 Operations research, mathematical programming (90-XX) 1,193 Information and communication theory, circuits (94-XX) 1,077 Mathematical logic and foundations (03-XX) 768 Numerical analysis (65-XX) 630 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 453 Convex and discrete geometry (52-XX) 430 Biology and other natural sciences (92-XX) 400 Number theory (11-XX) 269 Statistics (62-XX) 263 Order, lattices, ordered algebraic structures (06-XX) 256 Probability theory and stochastic processes (60-XX) 221 Linear and multilinear algebra; matrix theory (15-XX) 184 Quantum theory (81-XX) 182 Systems theory; control (93-XX) 180 Group theory and generalizations (20-XX) 110 Dynamical systems and ergodic theory (37-XX) 103 Algebraic geometry (14-XX) 71 Geometry (51-XX) 60 Field theory and polynomials (12-XX) 59 Statistical mechanics, structure of matter (82-XX) 52 Commutative algebra (13-XX) 43 Measure and integration (28-XX) 41 General and overarching topics; collections (00-XX) 36 History and biography (01-XX) 33 Calculus of variations and optimal control; optimization (49-XX) 33 General topology (54-XX) 31 General algebraic systems (08-XX) 28 Category theory; homological algebra (18-XX) 27 Associative rings and algebras (16-XX) 24 Ordinary differential equations (34-XX) 23 Differential geometry (53-XX) 23 Manifolds and cell complexes (57-XX) 22 Real functions (26-XX) 22 Mechanics of particles and systems (70-XX) 21 Partial differential equations (35-XX) 20 Approximations and expansions (41-XX) 20 Mechanics of deformable solids (74-XX) 17 Difference and functional equations (39-XX) 15 Functions of a complex variable (30-XX) 14 Operator theory (47-XX) 12 Algebraic topology (55-XX) 12 Fluid mechanics (76-XX) 11 Functional analysis (46-XX) 11 Geophysics (86-XX) 9 Integral transforms, operational calculus (44-XX) 7 Nonassociative rings and algebras (17-XX) 7 Special functions (33-XX) 7 Classical thermodynamics, heat transfer (80-XX) 6 Topological groups, Lie groups (22-XX) 5 Sequences, series, summability (40-XX) 5 Optics, electromagnetic theory (78-XX) 4 Harmonic analysis on Euclidean spaces (42-XX) 4 Integral equations (45-XX) 4 Global analysis, analysis on manifolds (58-XX) 4 Mathematics education (97-XX) 3 Potential theory (31-XX) 2 Several complex variables and analytic spaces (32-XX) 1 Abstract harmonic analysis (43-XX)