×

zbMATH — the first resource for mathematics

Sudborough, Ivan Hal

Compute Distance To:
Author ID: sudborough.ivan-hal Recent zbMATH articles by "Sudborough, Ivan Hal"
Published as: Sudborough, I. H.; Sudborough, I. Hal; Sudborough, Ivan Hal
External Links: MGP
Documents Indexed: 72 Publications since 1974, including 1 Book

Publications by Year

Citations contained in zbMATH Open

57 Publications have been cited 613 times in 437 Documents Cited by Year
The vertex separation and search number of a graph. Zbl 0942.68641
Ellis, J. A.; Sudborough, I. H.; Turner, J. S.
74
1994
On the tape complexity of deterministic context-free languages. Zbl 0379.68054
Sudborough, I. H.
49
1978
On tape-bounded complexity classes and multihead finite automata. Zbl 0299.68031
Sudborough, I. H.
34
1975
Topological bandwidth. Zbl 0573.05052
Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H.
33
1985
Min Cut is NP-complete for edge weighted trees. Zbl 0657.68034
Monien, B.; Sudborough, I. H.
30
1988
A note on tape-bounded complexity classes and linear context-free languages. Zbl 0318.68048
Sudborough, I. H.
30
1975
On the diameter of the pancake network. Zbl 0888.68007
Heydari, Mohammad H.; Sudborough, I. Hal
28
1997
Improved dynamic programming algorithms for bandwidth minimization and the MinCut linear arrangement problem. Zbl 0556.68012
Gurari, Eitan M.; Sudborough, Ivan Hal
28
1984
Polynomial time algorithms for the min cut problem on degree restricted trees. Zbl 0603.68068
Chung, Moon-Jung; Makedon, Fillia; Sudborough, Ivan Hal; Turner, Jonathan
22
1985
On minimizing width in linear layouts. Zbl 0715.05012
Makedon, Fillia; Sudborough, Ivan Hal
20
1989
Complexity and decidability for chain code picture languages. Zbl 0565.68065
Sudborough, I. H.; Welzl, E.
19
1985
An \((18/11)n\) upper bound for sorting by prefix reversals. Zbl 1191.68219
Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W.
16
2009
One-way multihead writing finite automata. Zbl 0337.02023
Sudborough, I. Hal
16
1976
The membership and equivalence problems for picture languages. Zbl 0636.68117
Kim, Changwook; Sudborough, Ivan Hal
14
1987
Bounded-reversal multihead finite automata languages. Zbl 0282.68033
Sudborough, I. Hal
14
1974
Time and tape bounded auxiliary pushdown automata. Zbl 0366.68037
Sudborough, I. H.
13
1977
The complexity of the membership problem for some extensions of context- free languages. Zbl 0398.68037
Sudborough, I. H.
12
1977
Bounding prefix transposition distance for strings and permutations. Zbl 1253.68145
Chitturi, Bhadrachalam; Sudborough, I. Hal
10
2012
Min cut is NP-complete for edge weighted trees. Zbl 0594.68042
Monien, B.; Sudborough, I. H.
10
1986
Minimizing width in linear layouts. Zbl 0514.94025
Makedon, F. S.; Sudborough, I. H.
10
1983
Simulating binary trees on hypercubes. Zbl 0652.68086
Monien, Burkhard; Sudborough, I. Hal
9
1988
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. Zbl 0493.68046
Monien, Burkhard; Sudborough, Ivan Hal
9
1982
Near embeddings of hypercubes into Cayley graphs on the symmetric group. Zbl 1395.05079
Miller, Zevi; Pritikin, Dan; Sudborough, I. Hal
8
1994
Bounding the bandwidth of NP-complete problems. Zbl 0454.68072
Monien, Burkhard; Sudborough, Ivan Hal
8
1981
On reversal-bounded picture languages. Zbl 0754.68068
Kim, Changwook; Sudborough, Ivan Hal
6
1992
Bandwidth contrained NP-complete problems. Zbl 0618.68043
Monien, Burkhard; Sudborough, Ivan Hal
6
1985
Bandwidth and pebbling. Zbl 0509.90100
Rosenberg, A. L.; Sudborough, I. H.
6
1983
Some remarks on multihead automata. Zbl 0369.68035
Sudborough, I. H.
6
1977
Extending permutation arrays: improving MOLS bounds. Zbl 1359.05002
Bereg, Sergey; Morales, Linda; Sudborough, I. Hal
5
2017
Short proofs for cut-and-paste sorting of permutations. Zbl 1128.05001
Cranston, Daniel W.; Sudborough, I. Hal; West, Douglas B.
5
2007
Bandwidth constraints on problems complete for polynomial time. Zbl 0535.68021
Sudborough, Ivan Hal
5
1983
On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store. Zbl 0365.68077
Sudborough, I. H.
5
1976
Constructing permutation arrays from groups. Zbl 1396.05003
Bereg, Sergey; Levy, Avi; Sudborough, I. Hal
4
2018
Embedding grids into hypercubes. Zbl 0794.68003
Bettayeb, Said; Miller, Zevi; Sudborough, I. Hal
4
1992
Block sorting is hard. Zbl 1075.68577
Bein, Wolfgang W.; Larmore, Lawrence L.; Latifi, Shahram; Sudborough, I. Hal
3
2003
Hamilton decompositions and \((n/2)\)-factorizations of hypercubes. Zbl 1027.05077
Bass, Douglas W.; Sudborough, I. Hal
3
2003
Expansion of layouts of complete binary trees into grids. Zbl 1046.68080
Lin, Y.-B.; Miller, Z.; Perkel, M.; Pritikin, D.; Sudborough, I. H.
3
2003
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. Zbl 0433.68043
Monien, Burkhard; Sudborough, Ivan Hal
3
1979
On families of languages defined by time-bounded random access machines. Zbl 0356.68058
Sudborough, I. H.; Zalcberg, A.
3
1976
Pancake problems with restricted prefix reversals and some corresponding Cayley networks. Zbl 1055.68005
Bass, Douglas W.; Sudborough, I. Hal
2
2003
Comparing star and pancake networks. Zbl 1026.68501
Morales, Linda; Sudborough, I. Hal
2
2002
Leftmove-bounded picture languages. Zbl 0939.68163
Kim, C.; Sudborough, I. H.
2
2000
Embedding star networks into hypercubes. Zbl 1068.68674
Bettayeb, Saïd; Cong, Bin; Girou, Mike; Sudborough, I. Hal
2
1996
Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group. Zbl 0860.68079
Miller, Z.; Pritikin, D.; Sudborough, I. H.
2
1996
Simulation of binary trees and \(X\)-trees on pyramid networks. Zbl 0783.68013
Dingle, Adair; Sudborough, I. Hal
2
1993
Deterministic message routing in faulty hypercubes. Zbl 0767.68008
Madhavapeddy, Seshu; Sudborough, I. Hal
2
1992
A polynomial algorithm for recognizing bounded cutwidth in hypergraphs. Zbl 0717.68047
Miller, Zevi; Sudborough, I. H.
2
1991
Disjoint paths in the hypercube. Zbl 0768.68163
Madhavapeddy, Seshu; Sudborough, I. Hal
2
1990
Complete problems for space bounded subclasses of NP. Zbl 0576.68031
Chung, Moon-Jung; Evangelist, W. Michael; Sudborough, Ivan Hal
2
1985
Topological bandwidth. Zbl 0539.68059
Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H.
2
1983
The time and tape complexity of developmental languages. Zbl 0357.68052
Sudborough, I. H.
2
1977
Calibrating an embedded protocol on an asynchronous system. Zbl 1188.68074
Yamauchi, Yukiko; Bein, Doina; Masuzawa, Toshimitsu; Morales, Linda; Sudborough, I. Hal
1
2008
A faster and simpler 2-approximation algorithm for block sorting. Zbl 1122.68740
Bein, Wolfgang W.; Larmore, Lawrence L.; Morales, Linda; Sudborough, I. Hal
1
2005
One-to-many embeddings of hypercubes into Cayley graphs generated by reversals. Zbl 0993.68074
Gardner, L.; Miller, Z.; Pritikin, D.; Sudborough, I. H.
1
2001
Compressing grids into small hypercubes. Zbl 0811.90111
Miller, Zevi; Sudborough, I. H.
1
1994
On the complexity of tree embedding problems. Zbl 0768.68059
Simonson, Shai; Sudborough, I. Hal
1
1992
“Cutwidth” and related graph problems. Zbl 1023.68647
Sudborough, I. Hal
1
1987
Constructing permutation arrays from groups. Zbl 1396.05003
Bereg, Sergey; Levy, Avi; Sudborough, I. Hal
4
2018
Extending permutation arrays: improving MOLS bounds. Zbl 1359.05002
Bereg, Sergey; Morales, Linda; Sudborough, I. Hal
5
2017
Bounding prefix transposition distance for strings and permutations. Zbl 1253.68145
Chitturi, Bhadrachalam; Sudborough, I. Hal
10
2012
An \((18/11)n\) upper bound for sorting by prefix reversals. Zbl 1191.68219
Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W.
16
2009
Calibrating an embedded protocol on an asynchronous system. Zbl 1188.68074
Yamauchi, Yukiko; Bein, Doina; Masuzawa, Toshimitsu; Morales, Linda; Sudborough, I. Hal
1
2008
Short proofs for cut-and-paste sorting of permutations. Zbl 1128.05001
Cranston, Daniel W.; Sudborough, I. Hal; West, Douglas B.
5
2007
A faster and simpler 2-approximation algorithm for block sorting. Zbl 1122.68740
Bein, Wolfgang W.; Larmore, Lawrence L.; Morales, Linda; Sudborough, I. Hal
1
2005
Block sorting is hard. Zbl 1075.68577
Bein, Wolfgang W.; Larmore, Lawrence L.; Latifi, Shahram; Sudborough, I. Hal
3
2003
Hamilton decompositions and \((n/2)\)-factorizations of hypercubes. Zbl 1027.05077
Bass, Douglas W.; Sudborough, I. Hal
3
2003
Expansion of layouts of complete binary trees into grids. Zbl 1046.68080
Lin, Y.-B.; Miller, Z.; Perkel, M.; Pritikin, D.; Sudborough, I. H.
3
2003
Pancake problems with restricted prefix reversals and some corresponding Cayley networks. Zbl 1055.68005
Bass, Douglas W.; Sudborough, I. Hal
2
2003
Comparing star and pancake networks. Zbl 1026.68501
Morales, Linda; Sudborough, I. Hal
2
2002
One-to-many embeddings of hypercubes into Cayley graphs generated by reversals. Zbl 0993.68074
Gardner, L.; Miller, Z.; Pritikin, D.; Sudborough, I. H.
1
2001
Leftmove-bounded picture languages. Zbl 0939.68163
Kim, C.; Sudborough, I. H.
2
2000
On the diameter of the pancake network. Zbl 0888.68007
Heydari, Mohammad H.; Sudborough, I. Hal
28
1997
Embedding star networks into hypercubes. Zbl 1068.68674
Bettayeb, Saïd; Cong, Bin; Girou, Mike; Sudborough, I. Hal
2
1996
Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group. Zbl 0860.68079
Miller, Z.; Pritikin, D.; Sudborough, I. H.
2
1996
The vertex separation and search number of a graph. Zbl 0942.68641
Ellis, J. A.; Sudborough, I. H.; Turner, J. S.
74
1994
Near embeddings of hypercubes into Cayley graphs on the symmetric group. Zbl 1395.05079
Miller, Zevi; Pritikin, Dan; Sudborough, I. Hal
8
1994
Compressing grids into small hypercubes. Zbl 0811.90111
Miller, Zevi; Sudborough, I. H.
1
1994
Simulation of binary trees and \(X\)-trees on pyramid networks. Zbl 0783.68013
Dingle, Adair; Sudborough, I. Hal
2
1993
On reversal-bounded picture languages. Zbl 0754.68068
Kim, Changwook; Sudborough, Ivan Hal
6
1992
Embedding grids into hypercubes. Zbl 0794.68003
Bettayeb, Said; Miller, Zevi; Sudborough, I. Hal
4
1992
Deterministic message routing in faulty hypercubes. Zbl 0767.68008
Madhavapeddy, Seshu; Sudborough, I. Hal
2
1992
On the complexity of tree embedding problems. Zbl 0768.68059
Simonson, Shai; Sudborough, I. Hal
1
1992
A polynomial algorithm for recognizing bounded cutwidth in hypergraphs. Zbl 0717.68047
Miller, Zevi; Sudborough, I. H.
2
1991
Disjoint paths in the hypercube. Zbl 0768.68163
Madhavapeddy, Seshu; Sudborough, I. Hal
2
1990
On minimizing width in linear layouts. Zbl 0715.05012
Makedon, Fillia; Sudborough, Ivan Hal
20
1989
Min Cut is NP-complete for edge weighted trees. Zbl 0657.68034
Monien, B.; Sudborough, I. H.
30
1988
Simulating binary trees on hypercubes. Zbl 0652.68086
Monien, Burkhard; Sudborough, I. Hal
9
1988
The membership and equivalence problems for picture languages. Zbl 0636.68117
Kim, Changwook; Sudborough, Ivan Hal
14
1987
“Cutwidth” and related graph problems. Zbl 1023.68647
Sudborough, I. Hal
1
1987
Min cut is NP-complete for edge weighted trees. Zbl 0594.68042
Monien, B.; Sudborough, I. H.
10
1986
Topological bandwidth. Zbl 0573.05052
Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H.
33
1985
Polynomial time algorithms for the min cut problem on degree restricted trees. Zbl 0603.68068
Chung, Moon-Jung; Makedon, Fillia; Sudborough, Ivan Hal; Turner, Jonathan
22
1985
Complexity and decidability for chain code picture languages. Zbl 0565.68065
Sudborough, I. H.; Welzl, E.
19
1985
Bandwidth contrained NP-complete problems. Zbl 0618.68043
Monien, Burkhard; Sudborough, Ivan Hal
6
1985
Complete problems for space bounded subclasses of NP. Zbl 0576.68031
Chung, Moon-Jung; Evangelist, W. Michael; Sudborough, Ivan Hal
2
1985
Improved dynamic programming algorithms for bandwidth minimization and the MinCut linear arrangement problem. Zbl 0556.68012
Gurari, Eitan M.; Sudborough, Ivan Hal
28
1984
Minimizing width in linear layouts. Zbl 0514.94025
Makedon, F. S.; Sudborough, I. H.
10
1983
Bandwidth and pebbling. Zbl 0509.90100
Rosenberg, A. L.; Sudborough, I. H.
6
1983
Bandwidth constraints on problems complete for polynomial time. Zbl 0535.68021
Sudborough, Ivan Hal
5
1983
Topological bandwidth. Zbl 0539.68059
Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H.
2
1983
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. Zbl 0493.68046
Monien, Burkhard; Sudborough, Ivan Hal
9
1982
Bounding the bandwidth of NP-complete problems. Zbl 0454.68072
Monien, Burkhard; Sudborough, Ivan Hal
8
1981
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. Zbl 0433.68043
Monien, Burkhard; Sudborough, Ivan Hal
3
1979
On the tape complexity of deterministic context-free languages. Zbl 0379.68054
Sudborough, I. H.
49
1978
Time and tape bounded auxiliary pushdown automata. Zbl 0366.68037
Sudborough, I. H.
13
1977
The complexity of the membership problem for some extensions of context- free languages. Zbl 0398.68037
Sudborough, I. H.
12
1977
Some remarks on multihead automata. Zbl 0369.68035
Sudborough, I. H.
6
1977
The time and tape complexity of developmental languages. Zbl 0357.68052
Sudborough, I. H.
2
1977
One-way multihead writing finite automata. Zbl 0337.02023
Sudborough, I. Hal
16
1976
On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store. Zbl 0365.68077
Sudborough, I. H.
5
1976
On families of languages defined by time-bounded random access machines. Zbl 0356.68058
Sudborough, I. H.; Zalcberg, A.
3
1976
On tape-bounded complexity classes and multihead finite automata. Zbl 0299.68031
Sudborough, I. H.
34
1975
A note on tape-bounded complexity classes and linear context-free languages. Zbl 0318.68048
Sudborough, I. H.
30
1975
Bounded-reversal multihead finite automata languages. Zbl 0282.68033
Sudborough, I. Hal
14
1974
all top 5

Cited by 589 Authors

26 Sudborough, Ivan Hal
12 Thilikos, Dimitrios M.
11 Fomin, Fedor V.
10 Yang, Boting
9 Bodlaender, Hans L.
9 Kim, Changwook
9 Nisse, Nicolas
8 Chitturi, Bhadrachalam
8 Ibarra, Oscar H.
8 Monien, Burkhard
8 Okhotin, Alexander
7 Dereniowski, Dariusz
7 Kutrib, Martin
7 Malcher, Andreas
7 Miller, Zevi
6 Fellows, Michael Ralph
6 Gurski, Frank
5 Dassow, Jürgen
5 Engelfriet, Joost
5 Fertin, Guillaume
5 Holzer, Markus
5 McKenzie, Pierre
5 Morales, Linda
5 Scarcello, Francesco
4 Bereg, Sergey N.
4 Coudert, David
4 Duarte, Abraham
4 Dyer, Danny D.
4 Hsu, Lihhsing
4 Huynh, Dung T.
4 Inoue, Katsushi
4 Kanté, Mamadou Moustapha
4 Leone, Nicola
4 Lokshtanov, Daniel
4 Mahajan, Meena
4 Pantrigo, Juan José
4 Rajasingh, Indra
4 Wendlandt, Matthias
4 Xue, Yuan
3 Bettayeb, Said
3 Borse, Y. M.
3 Brandenburg, Franz-Josef
3 Bulteau, Laurent
3 Buntrock, Gerhard
3 Chang, Jik Hyun
3 Chen, Genhuey
3 Costagliola, Gennaro
3 Dias, Zanoni
3 Ferrucci, Filomena
3 Fraigniaud, Pierre
3 Gottlob, Georg
3 Gravino, Carmine
3 Greibach, Sheila A.
3 Hromkovič, Juraj
3 Hsieh, Sun-Yuan
3 Jenner, Birgit
3 Kirousis, Lefteris Miltiades
3 Konstantinova, Elena V.
3 Kratsch, Dieter
3 Kwon, Ojoung
3 Langston, Michael A.
3 Lautemann, Clemens
3 Liu, Yanpei
3 Lohrey, Markus
3 Luccio, Flaminia L.
3 Makedon, Fillia
3 Manuel, Paul D.
3 Martí, Rafael
3 Mazauric, Dorian
3 Moriya, Etsuro
3 Müller, Haiko
3 Otto, Friedrich
3 Papadimitriou, Christos Harilaos
3 Pilipczuk, Michał
3 Ravikumar, Bala
3 Rethmann, Jochen
3 Rozenberg, Grzegorz
3 Sarbazi-Azad, Hamid
3 Simonson, Shai
3 Sudborough, Hal
3 Takanami, Itsuo
3 Wanke, Egon
3 Warmuth, Manfred K.
3 West, Douglas Brent
2 Abramovskaya, Tat’yana Viktorovna
2 Adler, Isolde
2 Allender, Eric W.
2 Arockiaraj, Micheal
2 Barash, Mikhail
2 Bein, Wolfgang W.
2 Blanco, Saúl A.
2 Blin, Lélia
2 Boasson, Luc
2 Buehrle, Charles
2 Caha, Rostislav
2 Cao, Yi
2 Chrobak, Marek
2 Chung Graham, Fan-Rong King
2 Cygan, Marek
2 da Fonseca, Guilherme Dias
...and 489 more Authors
all top 5

Cited in 65 Serials

110 Theoretical Computer Science
44 Discrete Applied Mathematics
36 Journal of Computer and System Sciences
32 Information Processing Letters
16 Discrete Mathematics
14 Information and Computation
11 Acta Informatica
11 Mathematical Systems Theory
10 Algorithmica
10 International Journal of Foundations of Computer Science
7 RAIRO, Informatique Théorique
7 RAIRO. Informatique Théorique et Applications
7 Theory of Computing Systems
7 Journal of Discrete Algorithms
6 Information Sciences
6 Journal of Combinatorial Optimization
6 Discrete Mathematics, Algorithms and Applications
5 Designs, Codes and Cryptography
4 Computers & Operations Research
4 International Journal of Computer Mathematics
3 Networks
3 SIAM Journal on Algebraic and Discrete Methods
3 Applied Mathematics. Series B (English Edition)
2 Applied Mathematics and Computation
2 Journal of Combinatorial Theory. Series B
2 Kybernetika
2 European Journal of Combinatorics
2 European Journal of Operational Research
2 Linear Algebra and its Applications
2 Computational Complexity
2 ACM Journal of Experimental Algorithmics
2 RAIRO. Theoretical Informatics and Applications
1 Computers & Mathematics with Applications
1 Computing
1 Journal of Algebra
1 Journal of Graph Theory
1 Journal of Soviet Mathematics
1 The Journal of Symbolic Logic
1 Kyungpook Mathematical Journal
1 Mathematica Slovaca
1 SIAM Journal on Computing
1 Advances in Applied Mathematics
1 Combinatorica
1 Journal of Symbolic Computation
1 Journal of Complexity
1 Formal Aspects of Computing
1 Annals of Operations Research
1 International Journal of Computational Geometry & Applications
1 Journal of Knot Theory and its Ramifications
1 The Australasian Journal of Combinatorics
1 Vestnik St. Petersburg University. Mathematics
1 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI
1 Combinatorics, Probability and Computing
1 Computational and Applied Mathematics
1 Annals of Mathematics and Artificial Intelligence
1 International Transactions in Operational Research
1 Mathematical Methods of Operations Research
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1
1 RAIRO. Theoretical Informatics and Applications
1 AKCE International Journal of Graphs and Combinatorics
1 Discrete Optimization
1 Frontiers of Mathematics in China
1 Computer Science Review
1 Journal of Applied Mathematics, Statistics and Informatics
1 Prikladnaya Diskretnaya Matematika

Citations by Year