Siegel der Universität
Universität zu Köln

Arbeitsgemeinschaft Diskrete Algorithmen (DIAL)

Publikationen

Randerath, B. und Vestergaard, P. D.

All P3-equipackable graphs.

Discrete Math. 310, no. 2, 355-359, 2010

 

Randerath, B. und Schiermeyer, I.

On maximum independent sets in P5-free graphs

Discrete Appl. Math. 158, 1041-1044, 2010

 

Chellali, M., Haynes, T.W., Randerath, B., Volkmann, L.

Bounds on the global offensive k-alliance number in graphs

Discussiones Mathematicae Graph Theory, Vol.29(3), 597-614, 2010

 

Fendrup, A., Henning, M. A. , Randerath, B. und Vestergaard, P. D.

An upper bound on the domination number of a graph with minimum degree 2

Discrete Math., Vol. 309 no. 4, 639-646, 2009  

 

Randerath, B. und Schiermeyer, I.

On Reed's Conjecture about ω, Δ and χ

Graph Theory Trends in Mathematics, Birkhäuser Verlag, 339-346, 2007  

 

Gerzen, T. und Randerath, B.

Factoring logic functions using star-colorings

Australas. J. Combin., Vol. 39, 115-127, 2007.

 

Le, V.B., Randerath, B. und Schiermeyer

On the complexity of 4-colouring graphs without long induced paths

Theoret. Comput. Sci.,. Vol. 389, 330-335, 2007.


Porschen, S., Randerath, B. und Speckenmeyer, E.

On Linear CNF Formulas

Lecture Notes in Computer Science 4121, 212-225, 2006. (9 th Intern. Symp. on the Theory and Appl. of Satisfiability Testing, SAT 2006, Seattle, 2006.)


Randerath, B., Vestergaard, P. D.

Well-covered graphs and factors

Discrete Appl. Math.,Vol. 154 (9), 1416-1428, 2006.


Randerath, B.

Domination cookies

Sonderband zum Ersten Aachener Tag der Graphentheorie RWTH Aachen, 2005


Porschen, S., Randerath, B. und Speckenmeyer, E.

Exact 3-satisfiability is decidable in time 20.16254n

Ann. Math. Artif. Intell., Vol. 43 (1-4), 173-193, 2005.


Randerath, B.

3-Colorability and forbidden subgraphs.I: characterizing pairs

Discrete Math., Vol. 276 (1-3), 313-325, 2004.


Randerath, B. und Schiermeyer, I.

3-colorability is in P for P6-free graphs

Discrete Appl. Math., Vol. 136 (2-3), 199-213, 2004.


Randerath, B. und Schiermeyer, I.

Vertex colouring and forbidden subgraphs - a survey

eingeladener Übersichtsartikel, Graphs and Combinatorics, Vol. 20 (1), 1-40, 2004.


Porschen, S., Randerath, B. und Speckenmeyer, E.

Linear time algorithms for some not-all-equal satisfiability problems

Lecture Notes in Computer Science 2919, 172-183, 2004. (6 th Intern. Symp. on the Theory and Appl. of Satisfiability Testing, SAT 2003, Santa Margherita Ligure, 2003.)


Le, V.B. und Randerath, B.

On stable cutsets in line graphs

Theoret. Comput. Sci.,. Vol. 301, 463-475, 2003.


Kochol, M., Lozin, V. und Randerath, B.

The 3-colorability problem on graphs with maximal degree 4

SIAM J. Comp., Vol. 32(5), 1128-1139, 2003.


Porschen, S., Randerath, B. und Speckenmeyer, E.

X3SAT decidable in time 2n/5

Extended Abstract in Proc. of 5 th Intern. Symp. on the Theory and Appl. of Satisfiability Testing (SAT 2002), Cinncinati, 2002.


Randerath, B., Schiermeyer, I., Tewes, M. und Volkmann, L.

Vertex pancyclic graphs

Discrete Appl. Math., Vol. 120 (1-3), 219-237, 2002.


Randerath, B., Schiermeyer, I. und Tewes, M.

3-colourability and forbidden subgraphs.II: polynomial algorithms

Discrete Math., Vol. 251 (1-3), 137-153, 2002.


Randerath, B. und Schiermeyer, I.

A note on Brooks' theorem for triangle-free graphs

Australas. J. Combin., Vol. 26, 3-9, 2002.


Randerath, B. und Schiermeyer, I.

Chromatic number of graphs each path of which is 3-colourable

Result. Math. 41, 150-155, 2002.

 

Randerath, B. und Vestergaard, P. D.

On well-covered graphs of odd girth 7 or greater

Discussiones Mathematicae Graph Theory, Vol.22, 159-172, 2002.

 

Randerath, B. und Schiermeyer, I.

3-colourability is in P for P6-free graphs

Extended Abstract in Electronic Notes in Discrete Math., Vol.8., 2001 (1st Cologne-Twente Workshop on Graphs and Comb. Optim., Köln, 2001.)

 

Randerath, B. und Schiermeyer, I.

Colouring graphs with prescribed induced cycle lengths

Discussiones Mathematicae Graph Theory, Vol.21, 267-282, 2001.

 

Harant, J., Jendrol, S., Randerath, B., Ryjacek, Z., Schiermeyer, I. und Voigt, M.

On weights of induced paths and cycles in claw-free and K1,r-free graphs

J. of Graph Theory, Vol.36 (3), 131-143, 2001.

 

Randerath, B.

3-Colourability and forbidden subgraphs.I: characterizing pairs

Ext. Abstract in Electronic Notes in Discrete Math., Vol. 5, 2000 (6th Intern. Conference on Graph Theory, Marseille, 2000.)

 

Randerath, B. und Volkmann, L.

Characterization of graphs with equal domination and matching number

Utilitas Math. , Vol. 55, 65-72, 1999.

 

Randerath, B., Schiermeyer, I. und Wang, H.

On quadrilaterals in a graph

Discrete Math. , Vol. 203, 229-237, 1999.

 

Randerath, B. und Schiermeyer, I.

Colouring graphs with prescribed induced cycle lengths

Extended Abstract in 10 th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), Baltimore, 1999.

 

Randerath, B., Schiermeyer, I., Tewes, M. und Volkmann, L.

Vertex-pancyclic graphs

Extended Abstract in Electronic Notes in Discrete Math., Vol. 3, 1999 (6 th Twente Workshop on Graphs and Comb. Optimization, Twente, 1999.)

 

Hoffmann, A., Randerath, B. und Volkmann, L.

Maximal sets of 2-factors in complete equipartite graphs

Extended Abstract in Electronic Notes in Discrete Math., Vol. 3, 1999. (6 th Twente Workshop on Graphs and Comb. Optimization, Twente, 1999.)

 

Niessen, T. und Randerath, B.

Regular factors of simple regular graphs, and factor-spectra

Discrete Math. , Vol. 185, 89-103, 1998.

 

Randerath, B. und Volkmann, L.

Characterization of graphs with equal domination and covering number

Discrete Math., Vol. 191,159-169, 1998.

 

Randerath, B. und Volkmann, L.

Simplicial graphs and relationships to different graph invariants

Ars Combin., Vol. 46, 211-217, 1997.

 

Randerath, B. und Volkmann, L.

A characterization of well-coverd block-cactus graphs

Australas. J. Combin. , Vol. 9, 307-314, 1994.

 

 

 

Bücher und Abschlußarbeiten

 

Randerath, B.

Wohlüberdecktheit in simplizialen und Blockkaktus-Graphen

Diplomarbeit, RWTH Aachen, 1993.

 

Randerath, B.

The Vizing bound for the chromatic number based on forbidden pairs

Dissertation, RWTH Aachen, Berichte aus der Mathematik, Shaker Verlag, 1998.

 

Mellin, S.

Polynomielle Färbungsalgorithmen für Pk-freie Graphen

Diplomarbeit, Universität zu Köln, 2002.

 

Gerzen,T.

Readnumber und Stararboricity auf speziellen Instanzklassen

Diplomarbeit, Universität zu Köln, 2003.

 

Randerath, B.

Graph colouring and satisfiability problems for restricted classes of instances

Habilitationsschrift, Universität zu Köln, 2004.

 

Holz, P.

Online-colouring of claw-free graphs by using first-fit

Diplomarbeit , Universität zu Köln, 2004.

 

Achter, V.

Radial level planarity in a propositional logic framework

Diplomarbeit , Universität zu Köln, 2005.

 

Küsters, D.

Potenzgraphen von phylogenetischen Bäumen

Diplomarbeit, Universität zu Köln, 2007.

 

Hoffmann, S.

Gleichpackbare Graphen

Diplomarbeit, Universität zu Köln, 2007.

 

Nieroda, L.

NAIS - New Automated Installation System. Conceptualization, design and implementation of an innovative hierarchic, decentralized system for large heterogeneous Beowulf clusters

Diplomarbeit , Universität zu Köln, 2007.

 

Zimmermann, Ch.

SAT-basierte Algorithmik polynomieller graphentheoretischer Probleme

Diplomarbeit, Universität zu Köln, 2008.

 

Rohrweck,T.

SAT-basierte Algorithmik NP-vollständiger graphentheoretischer Probleme

Diplomarbeit, Universität zu Köln, 2008.

 

Faigle, U. (ed.), Randerath, B. (ed.) und Schrader, R. (ed.)

Special issue: Papers of the 4th Cologne Twente workshop on graphs and combinatorial optimization, CTW 2005

Discrete Appl. Math. Vol. 156 no. 17, 3155-3338, 2008.

 

Hammersen, K.

Spiegelbilder in Graphen

Diplomarbeit, Universität zu Köln, 2008

 

Weil, V.

Über die Reed'sche Vermutung

Diplomarbeit, Universität zu Köln, 2008

 

Froning, T.

Die Erdös-Faudree Vermutung: Wangs Lösung

Diplomarbeit, Universität zu Köln, 2008

 

Thill, M.

Obere Schranken für die Ramseyzahl r(K3,G)

Diplomarbeit, RWTH Aachen, 2009

 

Schmidt, N.

Simulation von Mehrflugdienststunden und die daraus resultierende Simulation der Personalkapazitätssteuerung bei der Lufthansa CityLine

Diplomarbeit, Universität zu Köln, 2010

 

Werres, Ch.

Realisierung eines automatischen Entscheidungsunterstützungssystems im Performance Marketing

Diplomarbeit, Universität zu Köln, 2010