Algorithms and Complexity Group

Publications

2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998-1988

Publications in Journals (1992 - 1998)

Klaus Jansen
An approximation algorithm for the general routing problem
Information Processing Letters, 41, 333-339, 1992

Klaus Jansen
Processor-optimization for flow graphs
Theoretical Computer Science 104(2), 285-298, 1992

Klaus Jansen
The interconnection problem
Journal of Computer and System Science 46, 27-38, 1993

Klaus Jansen
Scheduling with constrained processor allocation for interval orders
Computers and Operations Research 20(6), 587-595, 1993

Klaus Jansen
Bounds for the general capacitated routing problem
Networks 23, 165-173, 1993

Klaus Jansen
The allocation problem in hardware-design
Discrete Applied Mathematics 43(1), 37-46, 1993

Klaus Jansen
Transfer flow graphs
Discrete Mathematics 115(1-3), 187-199, 1993

Klaus Jansen
One strike against the min-max degree triangulation problem
Computational Geometry 3, 107-120, 1993

Klaus Jansen and Gerhard Woeginger
The complexity of detecting crossingfree configurations in the plane 
BIT 33(4), 580-595, 1993

Klaus Jansen
Scheduling of incompatible jobs on unrelated machines
International Journal of Foundations of Computer Science 4(4), 275-291, 1993

Klaus Jansen
Exploiting the special structure of conflict graphs in high level synthesis
Commentationes Mathematicae Universitatis Carolinae 35(1) 155-167, 1994

Klaus Jansen
An approximation algorithm for the licence and shift class design problem
European Journal of Operational Research 73, 127-131, 1994

Klaus Jansen
Analysis of scheduling problems with typed task systems
Discrete Applied Mathematics 52(3), 223-232, 1994

Klaus Jansen
Integral flow with disjoint bundles
Nordic Journal of Computing 1(2), 264-267, 1994

Klaus Jansen
On the complexity of allocation problems in high-level synthesis
Integration, the VLSI Journal 17, 241-252, 1994

Hans L. Bodlaender, Klaus Jansen, and Gerhard Woeginger
Scheduling with incompatible jobs
Discrete Applied Mathematics 55(3), 219-232, 1994

Klaus Jansen
Scheduling of conditional executed jobs on unrelated processors
Discrete Applied Mathematics 61(3), 245-255, 1995

Klaus Jansen, Gerhard J. Woeginger, and Zhongliang Yu
UET scheduling with chain-type precedence constraints
Computers and Operations Research 22(9), 915-920, 1995

Klaus Jansen and Haiko Müller
The minimum broadcast time problem for several processor networks 
Theoretical Computer Science 147(1-2), 69-85, 1995

Klaus Jansen and Hans L. Bodlaender
Restrictions of graph partition problems 
Theoretical Computer Science 148(1), 93-109, 1995

Klaus Jansen
A rainbow about $T$-colorings for complete graphs
Discrete Mathematics 154(1-3), 129-139, 1996

Klaus Jansen, Petra Scheffler, and Gerhard J. Woeginger
The disjoint clique problem
RAIRO Operations Research 31, 45-66, 1997

Klaus Jansen and Petra Scheffler
Generalized coloring for tree-like graphs
Discrete Applied Mathematics 75(2), 135-155, 1997

Klaus Jansen and Sabine Öhring
Approximation algorithms for time constrained scheduling
Information and Computation 132(2), 85-108, 1997

Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza
Rankings of graphs
SIAM Journal on Discrete Mathematics 11(1), 168-181, 1998

Klaus Jansen and Joachim Reiter
Approximation algorithms for the register allocation problem
Integration, the VLSI Journal 25(2), 89-102, 1998

Klaus Jansen, Thomas Erlebach, Christos Kaklamanis, and Giuseppe Persiano
Directed tree networks
Encyclopedia of Optimization, Kluwer Academic Publisher

Publications in Conferences (1988-1998)

Klaus Jansen
Transformations of RT-descriptions guided by features of logic implementations to be verified
ABAKUS-Workshop, Innsbruck, 39-47, 1988

Klaus Jansen
An assignment problem for hardware design
Symposium on Operations Research (OR 1989),
Ulm 89, Methods of Operations Research 62, 263-272

Klaus Jansen
The processor optimization problem
Symposium on Operations Research (OR 1990),
Wien 90, Methods of Operations Research 64, 123-131

Klaus Jansen
Analysis of heuristics for the general capacitated routing problem
Symposium on Operations Research (OR 1991),
Stuttgart, Springer Verlag, 414-421

Klaus Jansen
Heuristics for several routing problems
Symposium on Operations Research (OR 1991),
Trier, Springer Verlag, 156-159

Klaus Jansen
Allocation in hardware design
IFIP Workshop on Control Dominated Synthesis from a RTL description (1992),
Grenoble, 81-86

Klaus Jansen
On scheduling problems restricted to interval orders
Graph Theoretic Concepts in Computer Science (WG1992),
Wiesbaden, LNCS 657, 27-36

Hans L. Bodlaender, Klaus Jansen, and Gerhard J. Woeginger
Scheduling with incompatible jobs
Graph Theoretic Concepts in Computer Science (WG1992),
Wiesbaden, LNCS 657, 37-49

Klaus Jansen and Petra Scheffler
Generalized coloring for tree-like graphs
Graph Theoretic Concepts in Computer Science (WG 1992),
Wiesbaden, LNCS 657, 50-59

Klaus Jansen and Hans L. Bodlaender
Restrictions of graph partition problems
Symposium on Operations Research (OR 1992),
Hamburg, Springer Verlag, 105-108

Klaus Jansen, Petra Scheffler, and Gerhard J. Woeginger
Maximum covering with D cliques
Fundamentals of Computation Theory (FCT 1993),
Szeged, LNCS 710, 319-328

Hans L. Bodlaender and Klaus Jansen
On the complexity of scheduling incompatible jobs with unit-times
 Mathematical Foundations of Computer Science (MFCS 1993),
Gdansk, LNCS 711, 291-300

Anders Dessmark, Klaus Jansen, and Andrzej Lingas
The maximum $k$-dependent and $f$-dependent set problem
Algorithms and Computation (ISAAC 1993),
Hongkong, LNCS 762, 88-98

Klaus Jansen
A rainbow about $T$-colorings for complete graphs
Graph Theoretic Concepts in Computer Science (WG 1993),
Utrecht, LNCS 790, 189-199

Hans L. Bodlaender, and Klaus Jansen 
On the complexity of the maximum cut problem
Symposium on Theoretical Aspects of Computer Science (STACS 1994),
Caen, LNCS 775, 769-780

Klaus Jansen and Haiko Müller
The minimum broadcast time problem on several processor networks
Parallel and Distributed Computing (1994),
Montreal, LNCS 805, 219-234

Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza
Ranking of graphs
Graph Theoretic Concepts in Computer Science (WG 1994),
München, LNCS 903, 292-304

Klaus Jansen and Sabine Öhring
Approximation algorithms for time constrained scheduling
Parallel Algorithms for Irregularly Structured Problems (IRREGULAR 1995),
Lyon, LNCS 980, 143-157

Thomas Erlebach and Klaus Jansen
Scheduling of virtual connections in fast networks
Parallel Systems and Algorithms (PASA 1996),
Jülich, World Scientific 1996, 13-32

Thomas Erlebach and Klaus Jansen
Call scheduling in trees, rings and meshes<
Hawaii International Conference on System Sciences (HICSS 1997),
Maui, Hawaii, Volume 1, 221-222

Klaus Jansen
The optimum cost chromatic partition problem
Algorithms and Complexity (CIAC 1997),
Rom, LNCS 1203, 25-36

Klaus Jansen
Approximation results for wavelength routing in directed trees
Workshop on Optics and Computer Science (WOCS 1997),
Geneva

Klaus Jansen and Joachim Reiter
A new approximation algorithm for the register allocation problem
Solving Irregularly Structured Problems in Parallel (IRREGULAR 1997),
Paderborn, LNCS 1253, 135-146

Christos Kaklamanis, Pino Persiano, Thomas Erlebach, and Klaus Jansen
Constrained bipartite edge coloring with applications to wavelength routing
Automata, Languages and Programming (ICALP 1997),
Bologna, LNCS 1265, 493-504

Klaus Jansen
Approximation results for the optimum cost chromatic partition problem
Automata, Languages and Programming (ICALP 1997),
Bologna, LNCS 1256, 727-737,
and DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Vol. 40, Network Design: Connectivity and Facilities Location 1997, 143-168

Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, and Pino Persiano
An optimal greedy algorithm for wavelength allocation in directed tree networks
DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Vol. 40, Network Design: Connectivity and Facilities Location 1997, 117-130

Thomas Erlebach and Klaus Jansen
Off-line and on-line call scheduling in stars and trees
Graph Theoretic Concepts in Computer Science (WG 1997),
Berlin, LNCS 1335, 199-213

Klaus Jansen
The mutual exclusion scheduling problem for permutation and comparability graphs
Symposium on Theoretical Aspects of Computer Science (STACS 1998),
Paris, LNCS 1373, 287-297

Klaus Jansen
A new characterization of parity graphs and coloring problem with costs
Latin American Theoretical Informatics (LATIN 1998),
Campinas, LNCS 1380, 249-260

Klaus Jansen
An approximation scheme for bin packing with conflicts
Skandinavian Workshop on Algorithm Theory (SWAT 1998),
Stockholm, LNCS 1432, 35-46

Thomas Erlebach and Klaus Jansen
Efficient implementation of an optimal greedy algorithm for wavelength assignment in directed tree networks
Workshop on Algorithm Engineering (WAE 1998),
Saarbrücken, Technical Report MPI-I-98-1-019, pages 13-24

Klaus Jansen and José D. R. Rolim
Algorithms based on randomization and linear and semidefinite programming
Seminar on Current Trends in Theory and Practice of Informatics (SOFSEM 1998),
Jasna, LNCS 1521, 122-134

Thomas Erlebach and Klaus Jansen
Maximizing the number of connections in optical tree networks
International Symposium on Algorithms and Computation (ISAAC 1998),
Taejon, LNCS 1533, 179-189

Copyright

Copyright and all rights concerning the documents distributed by this server rest with the authors or other copyright holders. They may not be reposted without the copyright holders' explicit permission. The authors offer these documents here solely to ensure that others working in the same field have ready access to their scholarly or technical work on a noncommercial basis, and on condition that all users copying these documents do so respecting the terms and constraints set by the copyright.