Author Publications

2013

Broersma, Hajo and Kratsch, Dieter and Woeginger, Gerhard J. (2013) Fully decomposable split graphs. European journal of combinatorics, 34 (3). pp. 567-575. ISSN 0195-6698

2011

Brueggemann, Tobias and Hurink, Johann and Vredeveld, Tjark and Woeginger, Gerhard J. (2011) Exponential size neighborhoods for makespan minimization scheduling. Naval Research Logistics, 58 (8). pp. 795-803. ISSN 0894-069X

2009

Broersma, Hajo and Kratsch, Dieter and Woeginger, Gerhard J. (2009) Fully decomposable split graphs. In: 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, June 28 - July 2 2009, Hradec nad Moravicí, Czech Republic.

2008

Brouwer, Andries E. and Post, Gerhard F. and Woeginger, Gerhard J. (2008) Tight bounds for break minimization in tournament scheduling. Journal of Combinatorial Theory, Series A, 115 (6). pp. 1065-1068. ISSN 0097-3165

Brueggemann, T. and Hurink, J.L. and Vredeveld, T. and Woeginger, G.J. (2008) Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines. In: 5th International Workshop on Approximation and Online Algorithms, October 11-12, 2007, Eilat, Israel.

2007

Broersma, H.J. and Fomin, F.V. and Královič, R. and Woeginger, G.J. (2007) Eliminating graphs by means of parallel knock-out schemes. Discrete Applied Mathematics, 155 (2). pp. 92-102. ISSN 0166-218X

Broersma, Hajo and Fomin, Fedor V. and Golovach, Petr A. and Woeginger, Gerhard J. (2007) Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory, 55 (2). pp. 137-152. ISSN 0364-9024

Brouwer, Andries E. and Post, Gerhard and Woeginger, Gerhard J. (2007) Tight bounds for break minimization. [Report]

Kern, Walter and Woeginger, Gerhard (2007) Quadratic programming and combinatorial minimum weight product problems. Mathematical programming, 110 (3). pp. 641-649. ISSN 0025-5610

2006

Boucherie, R.J. and Bumb, A.F. and Endrayanto, A.I. and Woeginger, G.J. (2006) A combinatorial approximation algorithm for CDMA downlink rate allocation. In: Telecommunications planning: innovations in pricing, network design and management. Operations Research/Computer Science Interfaces, 33 . Springer, Berlin, pp. 275-293. ISBN 9780387292229

Broersma, H.J. and Fomin, F.V. and Kratochvil, J. and Woeginger, G.J. (2006) Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult. Algorithmica, 44 (4). pp. 343-361. ISSN 0178-4617

Brueggemann, T. and Hurink, J.L. and Vredeveld, T. and Woeginger, G.J. (2006) Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines. [Report]

Brueggemann, Tobias and Vredeveld, Tjark and Woeginger, Gerhard J. (2006) Performance of a Very Large-Scale Neighborhood for Minimizing Makespan on Parallel Machines. Electronic Notes in Theoretical Computer Science, 25 (1). pp. 29-33. ISSN 1571-0661

Kern, Walter and Woeginger, Gerhard (2006) Quadratic programming and combinatorial minimum weight product problems. In: 6th Italian Conference on Algorithms and Complexity, CIAC 2006, May 29-31, 2006, Rome, Italy.

Post, G.F. and Woeginger, G.J. (2006) Sports tournaments, home–away assignments, and the break minimization problem. Discrete Optimization, 3 (2). pp. 165-173. ISSN 1572-5286

2005

Broersma, H.J. and Paulusma, D. and Smit, G.J.M. and Vlaardingerbroek, F. and Woeginger, G.J. (2005) The computational complexity of the minimum weight processor assignment problem. In: 30th International Workshop on Graph-Theoretic Concepts in Computer Science, June 21-23, 2004, Bad Honnef, Germany.

Post, G.F. and Woeginger, G.J. (2005) Sports tournaments, home-away assignments, and the break minimization problem. [Report]

2004

Azar, Yossi and Epstein, Leah and Richter, Yossi and Woeginger, Gerhard J. (2004) All-norm approximation algorithms. Journal of Algorithms, 52 (2). pp. 120-133. ISSN 0196-6774

Boucherie, R.J. and Bumb, A.F. and Endrayanto, A.I. and Woeginger, G.J. (2004) A combinatorial approximation algorithm for CDMA downlink rate allocation. [Report]

Hurkens, Cor A.J. and Woeginger, Gerhard J. (2004) On the nearest neighbor rule for the traveling salesman problem. Operations Research Letters, 32 (1). pp. 1-4. ISSN 0167-6377

Klinz, Bettina and Woeginger, Gerhard J. (2004) Minimum-cost dynamic flows: The series-parallel case. Networks, 43 (3). pp. 153-162. ISSN 0028-3045

Král, Daniel and Majerech, Vladan and Sgall, Jiií and Tichy, Tomass and Woeginger, Gerhard (2004) It is tough to be a plumber. Theoretical Computer Science, 313 (3). pp. 473-484. ISSN 0304-3975

Woeginger, Gerhard J. (2004) Approximations through relaxations. Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica . pp. 12-18.

Woeginger, Gerhard J. (2004) Seventeen lines and one-hundred-and-one points. Theoretical Computer Science, 321 (2-3). pp. 415-421. ISSN 0304-3975

2003

Akker van den, Marjan and Hoogeveen, Han and Woeginger, Gerhard J. (2003) The two-machine open shop problem: To fit or not to fit, that is the question. Operations Research Letters, 31 (3). pp. 219-224. ISSN 0167-6377

Bonsma, Paul and Brueggemann, Tobias and Woeginger, Gerhard J. (2003) A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. In: 28th International Symposium on Mathematical Foundations of Computer Science, MFCS, August 25-29, 2003, Bratislava, Slovakia.

Born, Axel and Hurkens, Cor A.J. and Woeginger, Gerhard J. (2003) How to detect a counterfeit coin: Adaptive versus non-adaptive solutions. Information Processing Letters, 86 (3). pp. 137-141. ISSN 0020-0190

Broersma, H.J. and Fomin, F.V. and Golovach, P.A. and Woeginger, G.J. (2003) Backbone colorings for networks: tree and path backbones. [Report]

Broersma, H.J. and Fomin, F.V. and Kratochvil, J. and Woeginger, G.J. (2003) Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. [Report]

Broersma, Hajo and Faigle, Ulrich and Hurink, Johann and Pickl, Stefan and Woeginger, Gerhard (2003) Preface. In: 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Electronic Notes in Discrete Mathematics, 13 . Elsevier, p. 1.

Brüggemann, Tobias and Monnot, Jérôme and Woeginger, Gerhard J. (2003) Local search for the minimum label spanning tree problem with bounded color classes. Operations Research Letters (3). pp. 195-201. ISSN 0167-6377

Chrobak, Marek and Couperus, Peter and Dürr, Christoph and Woeginger, Gerhard (2003) On tiling under tomographic constraints. Theoretical Computer Science, 290 (3). pp. 2125-2136. ISSN 0304-3975

Deineko, Vladimir G. and Klinz, Bettina and Woeginger, Gerhard J. (2003) Which matrices are immune against the transportation paradox? Discrete Applied Mathematics, 130 (3). pp. 495-501. ISSN 0166-218X

Deineko, Vladimir G. and Woeginger, Gerhard J. (2003) Complexity and approximability results for slicing floorplan designs. European Journal of Operational Research, 149 (3). pp. 533-539. ISSN 0377-2217

Fekete, Sándor P. and Skutella, Martin and Woeginger, Gerhard J. (2003) The complexity of economic equilibria for house allocation markets. Information Processing Letters, 88 (5). pp. 219-223. ISSN 0020-0190

Pendavingh, Rudi and Schuurman, Petra and Woeginger, Gerhard J. (2003) Recognizing DNA graphs is difficult. Discrete Applied Mathematics, 127 (1). pp. 85-94. ISSN 0166-218X

Rudnicki, P. and Woeginger, G.J. (2003) The Post correspondence problem over a unary alphabet. Applied Mathematics Letters, 16 (5). pp. 723-727. ISSN 0893-9659

Woeginger, Gerhard J. (2003) A note on scoring rules that respect majority in choice and elimination. Mathematical Social Sciences, 46 (3). pp. 347-354. ISSN 0165-4896

Woeginger, Gerhard J. (2003) A note on the complexity of determining optimal strategies in games with common payoffs. Mathematical methods of operations research, 58 (2). pp. 183-189. ISSN 1432-2994

Woeginger, Gerhard J. (2003) A new characterization of the majority rule. Economics Letters, 81 (1). pp. 89-94. ISSN 0165-1765

Woeginger, Gerhard J. (2003) Banks winners in tournaments are difficult to recognize. Social Choice and Welfare, 20 (3). pp. 523-528. ISSN 0176-1714

Woeginger, Gerhard J. (2003) On the approximability of average completion time scheduling under precedence constraints. Discrete Applied Mathematics, 131 (1). pp. 237-252. ISSN 0166-218X

Woeginger, Gerhard J. (2003) Computational problems without computation. Nieuw archief voor wiskunde, Ser. 5. vol. 4 (2). pp. 140-147. ISSN 0028-9825

2002

Bodlaender, H.L. and Broersma, H.J. and Fomin, F.V. and Pyatkin, A.V. and Woeginger, G.J. (2002) Radio labeling with pre-assigned frequencies. [Report]

Broersma, H.J. and Fomin, F.V. and Nešetřil, J. and Woeginger, G.J. (2002) More about subcolorings. [Report]

Csirik, János and Woeginger, Gerhard J. (2002) Resource augmentation for online bounded space bin packing. Journal of Algorithms, 44 (2). pp. 308-320. ISSN 0196-6774

Epstein, Leah and Noga, John and Woeginger, Gerhard J. (2002) On-line scheduling of unit time jobs with rejection: minimizing the total completion time. Operations Research Letters, 30 (6). pp. 415-420. ISSN 0167-6377

Faneyte, Diego B.C. and Spieksma, Frits C.R. and Woeginger, Gerhard J. (2002) A branch-and-price algorithm for a hierarchical crew scheduling problem. Naval Research Logistics, 49 (8). pp. 743-759. ISSN 0894-069X

Rader Jr, David J. and Woeginger, Gerhard J. (2002) The quadratic 0–1 knapsack problem with series–parallel support. Operations Research Letters, 30 (3). pp. 159-166. ISSN 0167-6377

Woeginger, Gerhard J. (2002) Embeddings of planar graphs that minimize the number of long-face cycles. Operations Research Letters, 30 (3). pp. 167-168. ISSN 0167-6377

Woeginger, Gerhard J. (2002) An efficient algorithm for a class of constraint satisfaction problems. Operations Research Letters, 30 (1). pp. 9-16. ISSN 0167-6377

2001

Deineko, Vladimir G. and Woeginger, Gerhard J. (2001) Hardness of approximation of the discrete time-cost tradeoff problem. Operations Research Letters, 29 (5). pp. 207-210. ISSN 0167-6377

Hoogeveen, Han and Woeginger, Gerhard J. (2001) A very difficult scheduling problem with communication delays. Operations Research Letters, 29 (5). pp. 241-245. ISSN 0167-6377

Woeginger, Gerhard J. (2001) Editorial: special issue on effcient scheduling algorithms. Journal of Scheduling, 4 (6). pp. 285-286. ISSN 1094-6136