# zbMATH — the first resource for mathematics

## Dahlhaus, Elias

Compute Distance To:
 Author ID: dahlhaus.elias Published as: Dahlhaus, Elias; Dahlhaus, E. External Links: MGP
 Documents Indexed: 51 Publications since 1982, including 1 Book
all top 5

#### Co-Authors

 18 single-authored 8 Karpinski, Marek 5 Makowsky, Johann-Andreas 5 Miller, Mirka 4 Manuel, Paul D. 3 Gustedt, Jens 3 McConnell, Ross M. 2 Broersma, Hajo J. 2 Dankelmann, Peter 2 Kloks, Ton 2 Warmuth, Manfred K. 1 Andreev, Alexander E. 1 Berry, Anne 1 Clementi, Andrea E. F. 1 Damaschke, Peter 1 De Agostino, Sergio 1 Duchet, Pierre 1 Gaifman, Haim 1 Goddard, Wayne Dean 1 Hajnal, Péter 1 Heggernes, Pinar 1 Horák, Peter 1 Israeli, Amos 1 Johnson, David Stifler 1 Kelsen, Pierre 1 Kratochvíl, Jan 1 Nivick, Mark B. 1 Papadimitriou, Christos Harilaos 1 Ryan, Joe 1 Seymour, Paul D. 1 Simonet, Geneviève 1 Swart, Henda C. 1 Yannakakis, Mihalis
all top 5

#### Serials

 9 Discrete Applied Mathematics 5 Theoretical Computer Science 3 Information Processing Letters 3 Journal of Algorithms 2 Journal of Computer and System Sciences 1 Discrete Mathematics 1 Ars Combinatoria 1 Notre Dame Journal of Formal Logic 1 SIAM Journal on Computing 1 Information and Computation 1 SIAM Journal on Discrete Mathematics 1 The Australasian Journal of Combinatorics 1 Discrete Mathematics and Theoretical Computer Science. DMTCS

#### Fields

 43 Computer science (68-XX) 25 Combinatorics (05-XX) 8 Mathematical logic and foundations (03-XX) 3 Operations research, mathematical programming (90-XX)

#### Citations contained in zbMATH Open

43 Publications have been cited 494 times in 459 Documents Cited by Year
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
1994
Membership for growing context-sensitive grammars is polynomial. Zbl 0625.68055
Dahlhaus, Elias; Warmuth, Manfred K.
1986
Efficient and practical algorithms for sequential modular decomposition. Zbl 1017.68154
Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.
2001
Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. Zbl 0961.68152
Dahlhaus, Elias
2000
The train marshalling problem. Zbl 0962.90009
Dahlhaus, Elias; Horak, Peter; Miller, Mirka; Ryan, Joseph F.
2000
Maximum $$h$$-colourable subgraph problem in balanced graphs. Zbl 1338.68098
Dahlhaus, Elias; Manuel, Paul D.; Miller, Mirka
1998
On strongly chordal graphs. Zbl 0659.05059
Dahlhaus, E.; Duchet, P.
1987
A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs. Zbl 0940.05064
Broersma, H. J.; Dahlhaus, E.; Kloks, T.
2000
Efficient parallel recognition algorithms of cographs and distance hereditary graphs. Zbl 0822.68079
Dahlhaus, Elias
1995
Matching and multidimensional matching in chordal and strongly chordal graphs. Zbl 0902.68146
Dahlhaus, Elias; Karpinski, Marek
1998
Minimal elimination ordering inside a given chordal graph. Zbl 0886.05103
Dahlhaus, Elias
1997
Efficient and practical modular decomposition. Zbl 1321.05255
Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.
1997
A linear time algorithm to recognize clustered planar graphs and its parallelization. Zbl 0905.05074
Dahlhaus, Elias
1998
Skolem normal forms concerning the least fixpoint. Zbl 0636.03033
Dahlhaus, Elias
1987
MAD trees and distance-hereditary graphs. Zbl 1022.05023
Dahlhaus, E.; Dankelmann, P.; Goddard, W.; Swart, H. C.
2003
Partially complemented representations of digraphs. Zbl 0994.68098
Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.
2002
Efficient parallel and linear time sequential split decomposition (extended abstract). Zbl 1044.05511
Dahlhaus, Elias
1994
Concerning two-adjacent context-free languages. Zbl 0608.68061
Dahlhaus, E.; Gaifman, H.
1985
A fast parallel algorithm for computing all maximal cliques in a graph and the related problems. Zbl 0656.68070
Dahlhaus, Elias; Karpinski, Marek
1988
On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs. Zbl 0782.68055
Dahlhaus, Elias; Hajnal, Péter; Karpinski, Marek
1993
Fast parallel recognition of ultrametrics and tree metrics. Zbl 0942.68799
Dahlhaus, Elias
1993
A characterization of strongly chordal graphs. Zbl 0956.05090
Dahlhaus, Elias; Manuel, Paul D.; Miller, Mirka
1998
A linear-time algorithm to compute a MAD tree of an interval graph. Zbl 1183.68415
Dahlhaus, Elias; Dankelmann, Peter; Ravi, R.
2004
The choice of programming primitives for SETL-like programming languages. Zbl 0587.68005
Dahlhaus, E.; Makowsky, J. A.
1986
Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree. Zbl 1155.68088
Berry, Anne; Dahlhaus, Elias; Heggernes, Pinar; Simonet, Geneviève
2008
Perfect matching for regular graphs is $$AC^ 0$$-hard for the general matching problem. Zbl 0743.68072
Dahlhaus, Elias; Karpinski, Marek
1992
Fast parallel algorithms for the clique separator decomposition. Zbl 0800.68623
Dahlhaus, Elias; Karpinski, Marek; Nivick, Mark B.
1990
Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes. Zbl 0789.68062
Dahlhaus, Elias
1993
Minimal elimination ordering for graphs of bounded degree. Zbl 0998.05061
Dahlhaus, Elias
2002
Reduction to NP-complete problems by interpretations. Zbl 0558.03019
Dahlhaus, Elias
1984
An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3. Zbl 0764.68048
Dahlhaus, Elias; Karpinski, Marek; Kelsen, Pierre
1992
The computation of the jump number of convex graphs. Zbl 0953.05510
Dahlhaus, Elias
1994
Algorithms for the treewidth and minimum fill-in of HHD-free graphs. Zbl 0890.68091
Broersma, H. J.; Dahlhaus, E.; Kloks, T.
1997
Computable directory queries. Zbl 0604.68109
Dahlhaus, E.; Makowsky, J. A.
1986
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph. Zbl 0938.68958
Dahlhaus, Elias; Karpinski, Marek
1994
Transversal partitioning in balanced hypergraphs. Zbl 0887.05039
Dahlhaus, Elias; Kratochvil, Jan; Manuel, Paul D.; Miller, Mirka
1997
Membership for growing context sensitive grammars is polynomial. Zbl 0595.68071
Dahlhaus, Elias; Warmuth, Manfred K.
1986
Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs. Zbl 0666.68033
Dahlhaus, Elias; Karpinski, Marek
1988
The parallel complexity of approximating the high degree subgraph problem. Zbl 0913.68095
Andreev, A. E.; Clementi, A.; Crescenzi, P.; Dahlhaus, E.; De Agostino, S.
1998
Minimum fill-in and treewidth for graphs modularly decomposable into chordal graphs. Zbl 0936.68075
Dahlhaus, Elias
1998
Query languages for hierarchic databases. Zbl 0765.68029
Dahlhaus, E.; Makowsky, J. A.
1992
A parallel algorithm for computing Steiner trees in strongly chordal graphs. Zbl 0810.68081
Dahlhaus, Elias
1994
The parallel solution of domination problems on chordal and strongly chordal graphs. Zbl 0803.05048
Dahlhaus, Elias; Damaschke, Peter
1994
Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree. Zbl 1155.68088
Berry, Anne; Dahlhaus, Elias; Heggernes, Pinar; Simonet, Geneviève
2008
A linear-time algorithm to compute a MAD tree of an interval graph. Zbl 1183.68415
Dahlhaus, Elias; Dankelmann, Peter; Ravi, R.
2004
MAD trees and distance-hereditary graphs. Zbl 1022.05023
Dahlhaus, E.; Dankelmann, P.; Goddard, W.; Swart, H. C.
2003
Partially complemented representations of digraphs. Zbl 0994.68098
Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.
2002
Minimal elimination ordering for graphs of bounded degree. Zbl 0998.05061
Dahlhaus, Elias
2002
Efficient and practical algorithms for sequential modular decomposition. Zbl 1017.68154
Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.
2001
Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. Zbl 0961.68152
Dahlhaus, Elias
2000
The train marshalling problem. Zbl 0962.90009
Dahlhaus, Elias; Horak, Peter; Miller, Mirka; Ryan, Joseph F.
2000
A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs. Zbl 0940.05064
Broersma, H. J.; Dahlhaus, E.; Kloks, T.
2000
Maximum $$h$$-colourable subgraph problem in balanced graphs. Zbl 1338.68098
Dahlhaus, Elias; Manuel, Paul D.; Miller, Mirka
1998
Matching and multidimensional matching in chordal and strongly chordal graphs. Zbl 0902.68146
Dahlhaus, Elias; Karpinski, Marek
1998
A linear time algorithm to recognize clustered planar graphs and its parallelization. Zbl 0905.05074
Dahlhaus, Elias
1998
A characterization of strongly chordal graphs. Zbl 0956.05090
Dahlhaus, Elias; Manuel, Paul D.; Miller, Mirka
1998
The parallel complexity of approximating the high degree subgraph problem. Zbl 0913.68095
Andreev, A. E.; Clementi, A.; Crescenzi, P.; Dahlhaus, E.; De Agostino, S.
1998
Minimum fill-in and treewidth for graphs modularly decomposable into chordal graphs. Zbl 0936.68075
Dahlhaus, Elias
1998
Minimal elimination ordering inside a given chordal graph. Zbl 0886.05103
Dahlhaus, Elias
1997
Efficient and practical modular decomposition. Zbl 1321.05255
Dahlhaus, Elias; Gustedt, Jens; McConnell, Ross M.
1997
Algorithms for the treewidth and minimum fill-in of HHD-free graphs. Zbl 0890.68091
Broersma, H. J.; Dahlhaus, E.; Kloks, T.
1997
Transversal partitioning in balanced hypergraphs. Zbl 0887.05039
Dahlhaus, Elias; Kratochvil, Jan; Manuel, Paul D.; Miller, Mirka
1997
Efficient parallel recognition algorithms of cographs and distance hereditary graphs. Zbl 0822.68079
Dahlhaus, Elias
1995
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
1994
Efficient parallel and linear time sequential split decomposition (extended abstract). Zbl 1044.05511
Dahlhaus, Elias
1994
The computation of the jump number of convex graphs. Zbl 0953.05510
Dahlhaus, Elias
1994
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph. Zbl 0938.68958
Dahlhaus, Elias; Karpinski, Marek
1994
A parallel algorithm for computing Steiner trees in strongly chordal graphs. Zbl 0810.68081
Dahlhaus, Elias
1994
The parallel solution of domination problems on chordal and strongly chordal graphs. Zbl 0803.05048
Dahlhaus, Elias; Damaschke, Peter
1994
On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs. Zbl 0782.68055
Dahlhaus, Elias; Hajnal, Péter; Karpinski, Marek
1993
Fast parallel recognition of ultrametrics and tree metrics. Zbl 0942.68799
Dahlhaus, Elias
1993
Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes. Zbl 0789.68062
Dahlhaus, Elias
1993
Perfect matching for regular graphs is $$AC^ 0$$-hard for the general matching problem. Zbl 0743.68072
Dahlhaus, Elias; Karpinski, Marek
1992
An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3. Zbl 0764.68048
Dahlhaus, Elias; Karpinski, Marek; Kelsen, Pierre
1992
Query languages for hierarchic databases. Zbl 0765.68029
Dahlhaus, E.; Makowsky, J. A.
1992
Fast parallel algorithms for the clique separator decomposition. Zbl 0800.68623
Dahlhaus, Elias; Karpinski, Marek; Nivick, Mark B.
1990
A fast parallel algorithm for computing all maximal cliques in a graph and the related problems. Zbl 0656.68070
Dahlhaus, Elias; Karpinski, Marek
1988
Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs. Zbl 0666.68033
Dahlhaus, Elias; Karpinski, Marek
1988
On strongly chordal graphs. Zbl 0659.05059
Dahlhaus, E.; Duchet, P.
1987
Skolem normal forms concerning the least fixpoint. Zbl 0636.03033
Dahlhaus, Elias
1987
Membership for growing context-sensitive grammars is polynomial. Zbl 0625.68055
Dahlhaus, Elias; Warmuth, Manfred K.
1986
The choice of programming primitives for SETL-like programming languages. Zbl 0587.68005
Dahlhaus, E.; Makowsky, J. A.
1986
Computable directory queries. Zbl 0604.68109
Dahlhaus, E.; Makowsky, J. A.
1986
Membership for growing context sensitive grammars is polynomial. Zbl 0595.68071
Dahlhaus, Elias; Warmuth, Manfred K.
1986
Concerning two-adjacent context-free languages. Zbl 0608.68061
Dahlhaus, E.; Gaifman, H.
1985
Reduction to NP-complete problems by interpretations. Zbl 0558.03019
Dahlhaus, Elias
1984
all top 5

#### Cited by 728 Authors

 19 Otto, Friedrich 12 Brandstädt, Andreas 11 Bentz, Cédric 11 Dahlhaus, Elias 10 Paul, Christophe 9 Durán, Guillermo Alfredo 9 Habib, Michel A. 8 Heggernes, Pinar 8 Lê Văn Băng 8 Szwarcfiter, Jayme Luiz 7 Papadopoulos, Charis 6 Kang, Liying 6 Nikolopoulos, Stavros D. 6 Safe, Martín Darío 6 Shan, Erfang 5 Bonomo, Flavia 5 Chandrasekaran, Karthekeyan 5 Corneil, Derek Gordon 5 Cornelsen, Sabine 5 Costa, Marie-Christine 5 Di Stefano, Gabriele 5 Jurdziński, Tomasz 5 Karpinski, Marek 5 Karzanov, Aleksandr V. 5 Kwon, Ojoung 5 Niedermeier, Rolf 5 Palios, Leonidas 5 Ries, Bernard 5 Roupin, Frédéric 5 Wagler, Annegret Katrin 4 Angelini, Patrizio 4 Bérczi, Kristóf 4 Berry, Anne 4 de Montgolfier, Fabien 4 Elbassioni, Khaled M. 4 Fomin, Fedor V. 4 Frati, Fabrizio 4 Golovach, Petr A. 4 Hirai, Hiroshi 4 Király, Tamás 4 Lee, Chuan-Min 4 Liang, Zuosong 4 Mahjoub, Ali Ridha 4 Mancini, Federico 4 McConnell, Ross M. 4 Mráz, František 4 Nichterlein, André 4 Rao, Michaël 3 Bodlaender, Hans L. 3 Boros, Endre 3 Boysen, Nils 3 Buchbinder, Niv 3 Cohen, David A. 3 Colin de Verdière, Éric 3 Cooper, Martin C. 3 Da Lozzo, Giordano 3 Damaschke, Peter 3 de Figueiredo, Celina M. Herrera 3 Demange, Marc 3 Di Battista, Giuseppe 3 Dragan, Feodor F. 3 Erdős, Péter L. 3 Galby, Esther 3 Gioan, Emeric 3 Gurvich, Vladimir A. 3 Hsieh, Sun-Yuan 3 Jaehn, Florian 3 Jeavons, Peter G. 3 Joeris, Benson L. 3 Kanté, Mamadou Moustapha 3 Kerivin, Hervé L. M. 3 Khachiyan, Leonid Genrikhovich 3 Kim, Eunjung 3 Li, Angsheng 3 Li, Xianyue 3 Lin, Min Chih 3 Lokshtanov, Daniel 3 Maffray, Frédéric 3 Martin, Sébastien 3 Marx, Dániel 3 Mertzios, George B. 3 Mosca, Raffaele 3 Nagy, Benedek 3 Ochem, Pascal 3 Pilipczuk, Marcin 3 Salomaa, Kai T. 3 Sampaio, Rudini Menezes 3 Schwartz, Roy 3 Simonet, Geneviève 3 Sritharan, R. 3 Székely, László A. 3 Van Leeuwen, Erik Jan 3 Vazirani, Vijay V. 3 Warmuth, Manfred K. 3 Xu, Chao 2 Agnarsson, Geir 2 Bandelt, Hans-Jürgen 2 Biha, Mohamed Didi 2 Brandes, Ulrik 2 Bredereck, Robert ...and 628 more Authors
all top 5

#### Cited in 86 Serials

 86 Discrete Applied Mathematics 61 Theoretical Computer Science 22 Algorithmica 18 Discrete Mathematics 18 Information Processing Letters 14 Journal of Computer and System Sciences 10 Information and Computation 10 Journal of Discrete Algorithms 9 SIAM Journal on Discrete Mathematics 9 International Journal of Foundations of Computer Science 9 Mathematical Programming. Series A. Series B 8 Theory of Computing Systems 8 Journal of Combinatorial Optimization 7 Discrete Optimization 6 SIAM Journal on Computing 6 International Journal of Computer Mathematics 5 Operations Research Letters 4 Journal of Graph Theory 4 Networks 4 European Journal of Combinatorics 4 European Journal of Operational Research 4 OR Spectrum 3 Artificial Intelligence 3 Graphs and Combinatorics 3 Discrete & Computational Geometry 3 Computers & Operations Research 3 Annals of Operations Research 3 Journal of Global Optimization 3 Discrete Mathematics, Algorithms and Applications 2 Acta Informatica 2 Computational Geometry 2 Pattern Recognition 2 International Journal of Computer Vision 2 Journal of Scheduling 2 RAIRO. Theoretical Informatics and Applications 2 Mathematics in Computer Science 2 RAIRO. Theoretical Informatics and Applications 2 Computer Science Review 2 ACM Transactions on Computation Theory 2 Prikladnaya Diskretnaya Matematika 1 Computers & Mathematics with Applications 1 International Journal of Heat and Mass Transfer 1 Israel Journal of Mathematics 1 Applied Mathematics and Computation 1 Computing 1 Journal of Combinatorial Theory. Series B 1 Journal of Pure and Applied Algebra 1 Mathematics of Operations Research 1 Mathematika 1 Cybernetics 1 Advances in Applied Mathematics 1 Journal of Classification 1 Optimization 1 Asia-Pacific Journal of Operational Research 1 Applied Mathematics Letters 1 Mathematical and Computer Modelling 1 Science in China. Series A 1 Games and Economic Behavior 1 ZOR. Zeitschrift für Operations Research 1 Cybernetics and Systems Analysis 1 Computational Optimization and Applications 1 Journal of Logic, Language and Information 1 Journal of Computer and Systems Sciences International 1 The Electronic Journal of Combinatorics 1 Annals of Mathematics and Artificial Intelligence 1 Mathematical Problems in Engineering 1 Soft Computing 1 Journal of Shanghai University 1 Annals of Combinatorics 1 Data Mining and Knowledge Discovery 1 Trudy Instituta Matematiki 1 Journal of Systems Science and Complexity 1 Journal of Applied Mathematics and Computing 1 Multiscale Modeling & Simulation 1 4OR 1 Acta Numerica 1 Advances in Data Analysis and Classification. ADAC 1 Logical Methods in Computer Science 1 Electronic Journal of Statistics 1 Acta Universitatis Sapientiae. Informatica 1 Algorithms 1 International Journal of Combinatorics 1 Mathematical Programming Computation 1 ISRN Discrete Mathematics 1 Journal of the Operations Research Society of China 1 The Art of Discrete and Applied Mathematics
all top 5

#### Cited in 24 Fields

 292 Computer science (68-XX) 282 Combinatorics (05-XX) 123 Operations research, mathematical programming (90-XX) 11 Biology and other natural sciences (92-XX) 10 Mathematical logic and foundations (03-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 5 Convex and discrete geometry (52-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 4 General topology (54-XX) 4 Information and communication theory, circuits (94-XX) 3 Manifolds and cell complexes (57-XX) 3 Statistics (62-XX) 3 Numerical analysis (65-XX) 3 Statistical mechanics, structure of matter (82-XX) 2 Probability theory and stochastic processes (60-XX) 2 Systems theory; control (93-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Associative rings and algebras (16-XX) 1 Group theory and generalizations (20-XX) 1 Real functions (26-XX) 1 Functions of a complex variable (30-XX) 1 Functional analysis (46-XX) 1 Fluid mechanics (76-XX) 1 Classical thermodynamics, heat transfer (80-XX)