zum Inhalt springen

Publikationen zwischen 2000 und 2009

2009

  • Porschen, Stefan: On rectangular covering problems. In: International Journal of Computational Geometry & Applications, Volume 19, 2009, pp. 325-340.
  • Porschen, Stefan; Schmidt, Tatjana; Speckenmeyer, Ewald: On Some Aspects of Mixed-Horn formulas. In: Lecture Notes in Computer Science, Volume 5584, 2009, pp. 86-100.
  • Porschen, Stefan; Speckenmeyer, Ewald; Zhao, Xishun: Linear CNF formulas and satisfiability. In: Discrete Applied Mathematics 157, 2009, pp. 1046-1068.
  • Porschen, Stefan; Schmidt, Tatjana: On Some SAT-variants over Linear Formulas. In: Lecture Notes in Computer Science, Volume 5404, 2009, pp. 449-460.
  • Porschen, Stefan: An FPT-variant of the Shadow Problem with kernelization. In: Proceedings of ICCS 2009, Hong Kong, 2009, pp. 432-439.

2008

  • Speckenmeyer, Ewald; Li, Chu Min; Manquinho, Vasco; Tacchella, Armando (Ed.): Special Issue in the 2007 Competitions. In: Journal on Satisfiability, Boolean Modeling and Computation, Volume 4, 2008.
  • Porschen, Stefan; Speckenmeyer, Ewald: A CNF Class Generalizing Exact Linear Formulas. In: Lecture Notes in Computer Science, Volume 4996, 2008, pp. 231-245.
  • Ullrich, Oliver; Speckenmeyer, Ewald: Parallelisierung der Simulation von ÖPNV-Netzen. Poster, 5. ASIM-Treffen Grundlagen und Methoden von Modellierung und Simulation, 18.-20. Februar 2008.
  • Niepel, Sebastian: Ganztagesfahrplanoptimierung im ÖPNV mit naturanalogen Methoden. Diplomarbeit, Univ. Köln, 2008.
  • Plagge, Galyna; Porschen, Stefan: Über Variablen-Gewichtete X3SAT-Probleme. In: Proceedings of 54. Workshop über Algorithmen und Komplexität, Universität Hannover, 5. März 2008.

2007

  • Porschen, Stefan; Speckenmeyer, Ewald: Algorithms for Variable-Weighted 2-SAT and Dual Problems. In: Lecture Notes in Computer Science, Volume 4501, 2007, pp. 173-186.
  • Porschen, Stefan: Structural and computational aspects of restricted Boolean formulas. Habilitationsschrift, Univ. Köln, 2007.
  • Porschen, Stefan: Optimal Parameterized Rectangular Coverings. In: Lecture Notes in Computer Science, Volume 4705, 2007, pp. 96-109.
  • Porschen, Stefan: On variable-weighted exact satisfiability problems. In: Annals of Mathematics and Artificial Intelligence, Volume 51, 2007, pp. 27-54.
  • Porschen, Stefan: A CNF Formula Hierarchy over the Hypercube. In: Lecture Notes in Computer Science, Volume 4830, 2007, pp. 234-243.
  • Porschen, Stefan; Speckenmeyer, Ewald: Clause set structures and satisfiability. Technical Report zaik2007-532, Univ. Köln, 2007.
  • Ullrich, Oliver: Mehr Pünktlichkeit im ÖPNV: Optimierung und Simulation des Kölner Stadtbahn-Fahrplans. Vortrag, Wissenschaft im Rathaus, Köln, 25. April 2007.
  • Schön, Andreas: Optimierung von Stadtbahnfahrplänen - Ein Genetischer Algorithmus sowie Simulation der Optimalfahrpläne unter Einbeziehung des neuen Kölner Nord-Süd-Stadtbahntunnels. Diplomarbeit, Univ. Köln, 2007.
  • Porschen, Stefan: On generalizations of the shadow independent set problem. In: Discrete Mathematics, Volume 37, 2007, pp. 1473-1785.
  • Porschen, Stefan; Speckenmeyer, Ewald: Satisfiability of mixed Horn formulas. In: Discrete Applied Mathematics, Volume 155, 2007, pp. 1408-1419.

2006

  • Porschen, Stefan: Algorithms for Rectangular Covering Problems. In: Lecture Notes in Computer Science, Volume 3980, 2006, pp. 40-49.
  • Ullrich, Oliver: CATSview - Eine Benutzerschnittstelle zur Steuerung, Visualisierung und Ergebnisauswertung von Fahrplansimulationen im ÖPNV. Diplomarbeit, Univ. Köln, 2006.
  • Porschen, Stefan; Speckenmeyer, Ewald; Randerath, Bert: On Linear CNF Formulas. In: Lecture Notes in Computer Science, Volume 4121, 2006, pp. 212-225.
  • Plagge, Galyna: Über Variablen-Gewichtete X3SAT Optimierungsprobleme. Diplomarbeit, Univ. Köln, 2006.
  • Porschen, Stefan; Speckenmeyer, Ewald: Linear CNF formulas and satisfiability. Technical Report zaik2006-520, Univ. Köln, 2006.
  • Porschen, Stefan: On variable-weighted exact satisfiability problems. Technical Report zaik2006-526, Univ. Köln, 2006.
  • Lückemeyer, Gero; Speckenmeyer, Ewald: Comparing Applicability of Two Simulation Models in Public Transport Simulation. In: Proceedings of 19. Symposium Simulationstechnik, Hannover, SCS Publishing House, San Diego,2006, pp. 9-14.
  • Porschen, Stefan; Speckenmeyer, Ewald: NP-completeness for Restricted Linear Formular Classes. In: Proceedings of Guangzhou Symposium on Satisfiability in Logical-Based Modeling, Technical Report, Sun Yat-sen University, Guangzhou, China, 2006, pp. 111-123.
  • Porschen, Stefan: Counting All Solutions of Minimum Weight Exact Satisfiability. In: Lecture Notes in Computer Science, Volume 3998, 2006, pp. 50-59.

2005

  • Porschen, Stefan; Speckenmeyer, Ewald: Worst Case Bounds for Some NP-Complete Modified Horn-SAT Problems. In: Lecture Notes in Computer Science, Volume 3542, 2005, pp. 251-262.
  • Porschen, Stefan; Speckenmeyer, Ewald: Satisfiability of Mixed Horn Formulas. Technical Report zaik2005-499, Univ. Köln, 2005.
  • Porschen, Stefan: Counting All Solutions of Minimum Weight Exact Satisfiability. Technical Report zaik2005-500, Univ. Köln, 2005.
  • Porschen, Stefan: A New Parameterization of the Shadow Problem. Technical Report zaik2005-501, Univ. Köln, 2005.
  • Achter, Viktor: Radial Level Planarity in a Propositional Logic Framework. Diplomarbeit, Univ. Köln, 2005.
  • Porschen, Stefan: Solving Minimum Weight Exact Satisfiability in Time O(2^0.2441n). In: Lecture Notes in Computer Science, Volume 3827, 2005, pp. 654-664.
  • Lückemeyer, Gero: A Traffic Simulation System Increasing the Efficiency of Schedule Design for Public Transport Systems Based on Scarce Data. Dissertation, Univ. Köln, 2005.
  • Randerath, Bert: Domination Cookies. In: Sonderband zum Ersten Aachener Tag der Graphentheorie, Shaker Verlag, 2005.
  • Randerath, Bert; Vestergaard, P. D.: Well-Covered Graphs and Factors. Accepted for publication in Discrete Applied Mathematics, 2005.
  • Porschen, Stefan; Randerath, Bert; Speckenmeyer, Ewald: Exact Satisfiability is Decidable in Time O(2^0.16254n). In: Annals of Mathematics and Artifical Intelligence, Volume 43(1-4), 2005, pp. 173-193.
  • Porschen, Stefan: On Some Weighted Satisfiability and Graph Problems. In: Lecture Notes in Computer Science, Volume 3381, 2005, pp. 278-287.
  • Porschen, Stefan: On the Rectangular Subset Closure of Point Sets. In: Lecture Notes in Computer Science, Volume 3480, 2005, pp. 796-805.
  • Rühmkorf, Jens: Entwicklung eines leistungsfähigen Lösers für Quantifizierte Boolesche Formeln. Diplomarbeit, Univ. Köln, 2005.
  • Randerath, B.; Schiermeyer, I.: Exact Algorithms for Minimum Dominating Set. Technical Report zaik2005-501, Univ. Köln, 2005.

2004

  • Randerath, Bert: 3-Colorability and Forbidden Subgraphs. I: Characterizing Pairs. In: Discrete Mathematics, Volume 276(1-3), 2004, pp. 313-325.
  • Porschen, Stefan; Speckenmeyer, Ewald: Satisfiability Problems for Mixed Horn Formulas. In: Proceedings of the Guangzhou Symposium on Satisfiability and its Applications, Guangzhou, China, September 2004, pp. 106-113.
  • Porschen, Stefan: On the Time Complexity of Rectangular Covering Problems in Discrete Plane. In: Lecture Notes in Computer Science, Volume 3045, 2004, pp. 137-146.
  • Holz, P.: Online-Colouring of Claw-Free Graphs by Using the Strategy of First-Fit. Diplomarbeit, Univ. Köln, 2004.
  • Kesavan Cheemplavam, P.: Optimierung der LBC auf Switched Ethernet. Diplomarbeit, Univ. Köln, 2004.
  • Randerath, Bert: Graph Colouring and Satisfiability Problems for Restricted Classes of Instances. Habilitationsschrift, Univ. Köln, 2004.
  • Speckenmeyer, Ewald: Robuste Straßenbahnfahrpläne - Reduktion der Verspätungsanfälligkeit. Vortragsreihe Universität im Rathaus, 29. November 2004.
  • Porschen, Stefan; Randerath, Bert; Speckenmeyer, Ewald: Linear Time Algorithms for Some Not-All-Equal Satisfiability Problems. In: Lecture Notes in Computer Science, Volume 2919, 2004, pp. 172-187.
  • Porschen, Stefan; Speckenmeyer, Ewald: Worst Case Bounds for Some Modified NP-Complete Horn-SAT Problems. Accepted for publication in Lecture Notes in Computer Science, Technical Report zaik2004-473, Univ. Köln, 2004.
  • Porschen, Stefan; Speckenmeyer, Ewald; Randerath, Bert; Gärtner, Mattias: Tabusat and WalkSat for Level Graph Formulas. Technical Report zaik2004-476, Univ. Köln, 2004.
  • Randerath, B.; Schiermeyer, I.: Vertex-Colouring and Forbidden Subgraphs - a Survey. In: Graphs and Combinatorics, Volume 20(1), 2004, pp. 1-40.
  • Randerath, B.; Schiermeyer, I.: 3-Colorability is in P for P6 - Free Graphs. In: Discrete Applied Mathematics, Volume 136(2-3), 2004.

2003

  • Randerath, B.; Schiermeyer, I.: Vertex-colouring and forbidden subgraphs - a survey. Technical Report zaik2003-453, Univ. Köln, 2003.
  • Porschen, Stefan; Randerath, Bert; Speckenmeyer, Ewald: Linear time algorithmus for some Not-All-Equal Satisfiability Problems. Accepted for publication in LNAI, Springer-Verlag, short version in: Proceedings of 6th international conference on Theory and Application of Satisfiability-Testing (SAT 2003), St. Margaritha Ligure-Portofino (Italy), 2003, pp. 72-80.
  • Franco, J.; Kleine Büning, H.; Speckenmeyer, E. (Editors): Results on Satisfiability in Propositional Logic. In: Annals of Mathematics and Artificial Intelligence, Volume 37, Number 3, Kluwer Academic Publishing, Dordrecht, 2003.
  • Speckenmeyer, E.; Franco, J.; van Maaren, H. (Editors): The Renesse Issue on Satisfiability. In: Discrete Applied Mathematics, Volume 130, Number 2, Elsevier, Amsterdam, 2003.
  • Porschen, Stefan: On the Rectangular Grid Hull of Point Sets and DAG's in the Plane. Technical Report zaik2004-463, Univ. Köln, 2003.
  • Heusch, Peter; Porschen, Stefan; Speckenmeyer, Ewald: Improving a fixed parameter tractability time bound for the shadow problem. In: Journal of Computer and System Sciences (JCSS), Volume 67, Number 4, 2003.
  • Genç, Zülfükar: Ein neuer Ansatz zur Fahrplanoptimierung im ÖPNV: Maximierung von zeitlichen Sicherheitabständen. Doktorarbeit, Univ. Köln, 2003.
  • Porschen, Stefan: Time Complexity of Rectangular Covering Problems in the Discrete Plane. Technical Report zaik2004-462, Univ. Köln, 2003.
  • Kochol, M.; Lozin, V.; Randerath, B.: The 3-colorability problem on graphs with maximal degree 4. In: SIAM Journal of Computing, Volume 32(5), 2003, pp. 1128-1139.
  • Le, V. B.; Randerath, B.: On Stable Cutsets in Line Graphs. In: Theoretical Computer Science, Volume 301, 2003, pp. 463-475.
  • Porschen, Stefan: A New Duality Principle for Hypergraphs and Propositional Formulas. Technical Report zaik2004-464, Univ. Köln, 2003.

2002

  • Randerath, B.; Schiermeyer, I.; Tewes, M.; Volkmann, L.: Vertex-Pancyclic Graphs. In: Discrete Applied Mathematics, Volume 120 (1-3), 2002, pp. 219-237.
  • Porschen, Stefan; Randerath, Bert; Speckenmeyer, Ewald: Exact 3-Satisfiability is decidable in time 0(2^0.16254n). Accepted for publication in: Annals of Mathematics and Artificial Intelligence, short version in: Proceedings of the 5th International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002), Cincinnati/Ohio, 2002, pp. 231-235.
  • Meisgen, Frank; Speckenmeyer, Ewald: A Dynamic Load Balancing Algorithmus with Adjustable Degree of Imbalance on Heterogeneous Network. In: Proceedings of 6th Workshop on Parallel Systems and Algorithms (PASA 2002), Karlsruhe, VDE, 2002, pp. 161-168.
  • Mellin, S.: Polynomielle Färbungsalgorithmen für Pk. Diplomarbeit, Univ. Köln, 2002.
  • Joisten, Martina: Simulation von Fahrplänen für den ÖPNV mittels Zellularautomaten. Diplomarbeit, Univ. Köln, 2002.
  • Porschen, Stefan: On Generalizations of the Shadow Independent Set Problem. Accepted for publication in Discrete Mathematics, Technical Report zaik2004-461, Univ. Köln, 2002.
  • Schwikowski, B.; Speckenmeyer, E.: On Computing all Minimal Solutions for Feedback Problems. In: Discrete Applied Mathematics, Volume 117, 2002, pp. 253-265.
  • Randerath, B., Vestergaard, P. D.: Well-Covered Graphs and Factors. Technical Report R-02-2017, Aalborg University, 2002.
  • Randerath, B., Vestergaard, P. D.: On Well-Covered Graphs of Odd Girth 7 or Greater. In: Discussiones Mathematicae Graph Theory, Volume 22, 2002, pp. 159-172.
  • Randerath, B., Schiermeyer, I.: Chromatic Number of Graphs Each Path of Which is 3-Colourable. In: Results in Mathematics, Volume 41, 2002, pp. 150-155.
  • Randerath, B., Schiermeyer, I.: A Note on Brooks' Theorem for Triangle-Free Graphs. In: Australasian Journal of Combinatorics, Volume 26, 2002, pp. 3-9.
  • Randerath, B., Schiermeyer, I., Tewes, M.: 3-Colourability and Forbidden Subgraphs. II: Polynomial Algorithms. In: Discrete Mathematics, Volume 251 (1-3), 2002, pp. 137-153.

2001

  • Harant, J.; Jendrol, S.; Randerath, B.; Ryjacek, Z.; Schiermeyer, I.; Voigt, M.: On Weights of Induced Paths and Cycles in Claw-Free and K1,r - Free Graphs. In: Journal of Graph Theory, Volume 36, Number 3, 2001, pp. 131-143.
  • Genç, Zülfükar; Speckenmeyer, Ewald: Fahrplanoptimierung im ÖPNV. Technical Report zaik2001-426, Univ. Köln, 2001.
  • Porschen, Stefan: On Covering Z-Grid Points by Rectangles. In: Electronic Notes in Discrete Mathematics, Volume 8, 2001.
  • Randerath, B.; Speckenmeyer, E.; Boros, E.; Cepek, O.; Hammer, P.; Kogan, A.; Makino, A.; Simeone, B.: A Satisfiability Formulation of Problems on Level Graphs. In: Proceedings of the LICS 2001 Workshop on Theory and Applications of Satisfiability Testing (SAT 2001), Boston/Massachusetts, June 14-15 2001, Kautz, H.; Selman, B. (Ed.), Electronic Notes in Discrete Mathematics, Volume 9, pp. 1-9.
  • Porschen, Stefan: Upper Bounds for Rectangular Covering Problems on Integer Lattices. Technical Report zaik2003-424, Univ. Köln, 2001.

2000

  • Lückemeyer, Gero: Datenmodellierung und Datenschnittstellen - Basis einer effizienten Fahrplangestaltung für den ÖPNV. Diplomarbeit, Univ. Köln, 2000.
  • Franco, J.; Gallo, G.; Kleine Büning, H.; Speckenmeyer, E. (Editors): Topics in Discrete Mathematics 10: The Satisfiability Problem. Elsevier, Amsterdam, 2000.