Prof. Dr. Stefan Hougardy

Please note that the papers on this page are preliminary versions that may differ from the final published versions.

Books

 
Buch Algorithmische Mathematik, 2. Auflage  S. Hougardy, J. Vygen
Algorithmische Mathematik
2. Auflage, Springer, Juli 2018
Weitere Informationen
      Book Algorithmic Mathematics  Algorithmic Mathematics
1st Edition, Springer Verlag, 2016
ISBN 978-3-319-39557-9
Informationen auf springer.com            
Book Algorithmic Mathematics Algorithmic Mathematics
Higher Education Press 2021
ISBN 978-7-04-053786-4




Refereed Publications

 
[60]
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem talk
SIAM Journal on Computing 52 (2023), 841-864 (with U. Brodowsky, X. Zhong)
[59]
A Fast Optimal Double Row Legalization Algorithm
ACM Transactions on Design Automation of Electronic Systems 28 (2023), Article 71, 26 pages (with M. Neuwohner, U. Schorr)
[58]
Hard to Solve Instances of the Euclidean Traveling Salesman Problem  code and data
Mathematical Programming Computation 13 (2021), 51-74 (with X. Zhong)
[57]
The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem  talk
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021),  18:1-18:15 (with U. Brodowsky)
[56]
A Fast Optimal Double Row Legalization Algorithm
ISPD '21 Proceedings of the 2021 ACM International Symposium on Physical Design (2021), 23-30 (with M. Neuwohner, U. Schorr)
[55]
BonnCell: Automatic Cell Layout in the 7-nm Era
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 39 (2020), 2872-2885 (with P. Van Cleeff,  J. Silvanus, T. Werner)
[54]
The Approximation Ratio of the 2-Opt Heuristic for the Metric Traveling Salesman Problem
Operations Research Letters 48 (2020), 401-404 (with F. Zaiser, X. Zhong)
[53]
Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
Mathematical Programming Computation 9(2) 2017, 135-202 (with J. Silvanus, J. Vygen)
[52]
Automatic Cell Layout in the 7nm Era
ISPD '17 Proceedings of the 2017 ACM International Symposium on Physical Design, 99-106  (with P.Cremer, J. Schneider, J. Silvanus)
[51]
An Exact Algorithm for Wirelength Optimal Placements in VLSI Design
Integration, the VLSI Journal 52 (2016),  355-366 (with J.Funke, J. Schneider)
[50]

On the Nearest Neighbor Rule for the Metric Traveling Salesman Problem
Discrete Applied Mathematics 195 (2015), 101-103 (with M. Wilde)
[49]
Chip Design
in: The Princeton Companion to Applied Mathematics, (N.J.Higham, ed.), Princeton University Press 2015, 804-807 (with S. Held, J. Vygen)
[48]
The Approximation Ratio of the Greedy Algorithm for the Metric Traveling Salesman Problem
Operations Research Letters 43 (2015), 259-261 (with J. Brecklinghaus)
[47]
Edge Elimination in TSP Instances log-files
In: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747,  Springer 2014, 275-286 (with R.T.Schroeder)
[46]
On the Integrality Ratio of the Subtour LP for Euclidean TSP
Operations Research Letters 42 (2014), 495-499
[45]
BonnCell: Automatic Layout of Leaf Cells
Proceedings of the 18th Asia and South Pacific Design Automation Conference (ASPDAC) 2013, 453-460 (with T.Nieberg, J.Schneider)
[44]
Wirelength Optimal Rectangle Packings
Proceedings of the fourth International Workshop on Bin Packing and Placement Constraints (BPPC'12) (with J.Funke, J. Schneider)
[43]
A Scale Invariant Algorithm for Packing Rectangles Perfectly
Proceedings of the fourth International Workshop on Bin Packing and Placement Constraints (BPPC'12)
[42]
On Packing Squares into a Rectangle    data and update (April 2014)
Computational Geometry 44 (2011),  456-463
[41]
Surface Realization with the Intersection Segment Functional
Experimental Mathematics 19:1 (2010), 79-92 (with F.H.Lutz, M.Zelke)
[40]
The Floyd-Warshall algorithm on graphs with negative cycles
Information Processing Letters 110 (2010), 279-281
[39]
Polyhedral Tori with Minimal Integer Coordinates
Electronic Geometry Model No. 2008.10.001 (2008) (with F.H.Lutz, M.Zelke)
[38]
Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
In: Research Trends in Combinatorial Optimization, W.J.Cook, L.Lovász, J.Vygen (Eds.), Springer 2008, 185-200
[37]
Polyhedra of Genus 3 with 10 Vertices and Minimal Coordinates
Electronic Geometry Model No. 2006.02.001 (2007) (with F.H.Lutz, M.Zelke)
[36]
Computation of Best Possible Low Degree Expanders
Discrete Applied Mathematics 155 (2007), 2539-2545 (with I.Köthnig)
[35]
Polyhedra of Genus 2 with 10 Vertices and Minimal Coordinates
Electronic Geometry Model No. 2005.08.001 (2007) (with F.H.Lutz, M.Zelke)
[34]
On a Conjecture of Hoàng and Tu Concerning Perfectly Orderable Graphs
Discrete Mathematics 306 (2006), 2962-2963
[33]
Classes of Perfect Graphs    update 22.4.2009
Discrete Mathematics 306 (2006), 2529-2571
[32]
Approximating Weighted Matchings in Parallel
Information Processing Letters, 99:3 (2006), 119-123 (with D.E.Vinkemeier)
[31]
Lower Bounds for the Relative Greedy Algorithm for Approximating Steiner Trees
Networks 47:2 (2006), 111-115 (with S.Kirchner)
[30]
Verfahren und Vorrichtung zum computergestützten Auffinden von ähnlichen Molekülen
Patent DE 10 2005 029 437 (2005) (with M.Thimm, V.Ziegler)
[29]
A Linear Time Approximation Algorithm for Weighted Matchings in Graphs
ACM Transactions on Algorithms, 1:1 (2005), 107-122 (with D.E. Drake Vinkemeier)
[28]
Perfectness is an Elusive Graph Property
SIAM Journal on Computing 34:1 (2004), 109-117 (with A.Wagler)
[27]
Comparison of 2D Similarity and 3D Superposition. Application to Searching a Conformational Drug Database
Journal of Chemical Information and Computer Sciences 44 (2004), 1816-1822 (with M.Thimm, A.Goede, R.Preissner)
[26] On Simplicial and co-Simplicial Vertices in Graphs
Discrete Applied Mathematics 138 (2004), 117-132 (with C.T. Hoàng, F. Maffray, N.V.R. Mahadev)
[25] On Approximation Algorithms for the Terminal Steiner Tree Problem
Information Processing Letters 89 (2004), 15–18 (with D.E.Drake)
[24] Accelerating Screening of 3D Protein Data with a Graph Theoretical Approach
Bioinformatics 19 (2003), 2442-2447 (with C.Frömmel, C.Gille, A.Goede, C.Gröpl, T.Nierhoff, R.Preißner, M.Thimm)
[23] Improved Linear Time Approximation Algorithms for Weighted Matchings
In: Approximation, Randomization, and Combinatorial Optimization, (Approx/Random 03), S.Arora, K.Jansen, J.D.P.Rolim, A.Sahai (Eds.), LNCS 2764, Springer 2003, 14-23 (with D.E.Drake)
[22] Linear Time Local Improvements for Weighted Matchings in Graphs
In: Experimental and Efficient Algorithms, K. Jansen, M. Margraf, M. Mastrolli, J.D.P.Rolim (Eds.), WEA 2003,  LNCS 2647, Springer 2003, 107-119 (with D.E.Drake)
[21] A Simple Approximation Algorithm for the Weighted Matching Problem
Information Processing Letters 85 (2003), 211-213 (with D.E.Drake)
[20] Recursive Generation of Partitionable Graphs
Journal of Graph Theory 41 (2002), 259-285 (with E.Boros, V.Gurvich)
[19] Steiner Trees in Uniformly Quasi-Bipartite Graphs
Information Processing Letters 83 (2002), 195–200  (with C.Gröpl, T.Nierhoff, H.J.Prömel)
[18] Polynomial Time Recognition of P4-structure
In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms 2002, 382 - 389 (with R.B.Hayward, B.A.Reed)
[17] Lower Bounds for Approximation Algorithms for the Steiner Tree Problem
In Graph-Theoretic Concepts in Computer Science, A. Brandstädt and V.B.Le (Eds.), 217-228, LNCS 2204, Springer Verlag  2001 (with C.Gröpl, T.Nierhoff, H.J.Prömel)
[16] Approximation Algorithms for the Steiner Tree Problem in Graphs
In: Steiner Trees in Industry,  X. Cheng and D.-Z. Du (Eds.), 235-279, Kluwer Academic Publishers, 2001 (with C.Gröpl, T.Nierhoff, H.J.Prömel)
[15] The P4-Structure of Perfect Graphs
In: Perfect Graphs, Jorge L. Ramírez-Alfonsín and Bruce A. Reed (Eds.), 93-112 , John Wiley & Sons, Inc. 2001
[14] On Wing Perfect Graphs
Journal of Graph Theory 31 (1999), 51-66
[13] A 1.598 Approximation Algorithm for the Steiner Problem in Graphs
In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms 1999, 448-453 (with H. J.Prömel)
[12] Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
Combinatorics, Probability & Computing 7 (1998), 375-386 (with Th.Emden-Weinert, B.Kreuter)
[11] Proof Checking and Non-Approximability
In Lectures on Proof Verification and Approximation Algorithms,  E.W.Mayr and H.J.Prömel and A.Steger (Eds.), 63-82, LNCS 1367,  Springer Verlag 1998
[10] Does the Jones-Polynomial Detect Unknottedness ?
Experimental Mathematics 6 (1997), 51-56 (with O.T.Dasbach)
[9] Perfect Graphs with Unique P4-Structure
Discrete Mathematics 165/166 (1997), 421-430
[8] Wing Triangulated Graphs are Perfect
Journal of Graph Theory 24 (1997), 25-31 (with V.B.Le, A.Wagler)
[7] A Conjecture of Kauffman on Amphicheiral Alternating Knots
Journal of Knot Theory and Its Ramifications, Vol.5, No. 5 (1996) 629-635 (with O.T.Dasbach)
[6] On the P4-Structure of Perfect Graphs V. Overlap Graphs
Journal of Combinatorial Theory,  Series B 67 (1996), 212-237 (with C.T.Hoàng, F.Maffray)
[5] On the P4-Structure of Perfect Graphs
Shaker Verlag, Aachen, 1996, ISBN 3-8265-1140-9
[4] Even Pairs and the Strong Perfect Graph Conjecture
Discrete Mathematics 154 (1996), 277-278
[3] Even and Odd Pairs in Linegraphs of Bipartite Graphs
European Journal of Combinatorics 16 (1995), 17-21
[2] Probabilistically Checkable Proofs and their Consequences for Approximation Algorithms
Discrete Mathematics 136 (1994), 175-223 ; reprinted in: Trends in Discrete Mathematics (W. Deuber, H.J. Prömel, B. Voigt, eds.), North
Holland, 1995. (with H.J.Prömel, A.Steger)
[1] Counterexamples to Three Conjectures Concerning Perfect Graphs
Discrete Mathematics 117 (1993), 245-251



Preprints and other Publications
 

The Bottom-Left Algorithm for the Strip Packing Problem
Report No : 241298, Research Institute for Discrete Mathematics, University of Bonn,  February 2024 (with Bart Zondervan)

The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5
Report No : 241297, Research Institute for Discrete Mathematics, University of Bonn,  February 2024 (with Sophia Heimann, Hung P. Hoang)

On the PLS-completeness of TSP/k-Opt
Report No : 231275, Research Institute for Discrete Mathematics, University of Bonn,  July 2023 (with Hung P. Hoang)

Local elimination in the traveling salesman problem
arXiv:2307.07054v1 [cs.DS] 13 Jul 2023 (with W. Cook, K. Helsgaun, R.Schroeder)

Dijkstra meets Steiner: computational results of a fast exact Steiner tree algorithm
Report No : 141092, Research Institute for Discrete Mathematics, University of Bonn, 2014 (with J. Silvanus, J. Vygen)
in: 11th DIMACS Implementation Challenge on Steiner Tree Problems, 2014

A Scale Invariant Exact Algorithm for Dense Rectangle Packing Problems
Report No: 101020,  Research Institute for Discrete Mathematics, University of Bonn,  June 2012

Packen von Rechtecken
Report No : 111035, Research Institute for Discrete Mathematics, University of Bonn, September 2011

Wirelength Optimal Results for the MCNC Block Packing Instances
Report No : 111029, Research Institute for Discrete Mathematics, University of Bonn, June 2011 (with J.Funke, J.Schneider)

New Approximation Algorithms for the Weighted Matching Problem
Report No : 101010,  Research Institute for Discrete Mathematics, University of Bonn, April 2010 (with S. Hanke)

Parallel Matching Algorithms
Oberwolfach Reports 3:1 (2006), 406-409

Approximation Algorithms for the Weighted Matching Problem
Oberwolfach Reports 1:3 (2004), 1499-1502

Approximating minimum spanning sets in hypergraphs and polymatroids
Humboldt-Universität zu Berlin, March 2000 (with G. Baudis, C. Gröpl, T. Nierhoff, H.J. Prömel)

Zelikovsky's 1+ln 2 Approximation Algorithm for the Steiner Problem in Graphs: A Simplified Analysis
April 1998, Humboldt-Universität zu Berlin (with H.J. Prömel)

Gasparian's Proof of the Perfect Graph Theorem
January 1997, Humboldt-Universität zu Berlin

The complexity of some problems on very sparse graphs
January 1997, Humboldt-Universität zu Berlin (with Th.Emden-Weinert, B.Kreuter)

Einführung in Graphen und Algorithmen
Skriptum, September 1996 (with Th.Emden-Weinert, B.Kreuter, H.J.Prömel, A.Steger)

Graph invariants and alternating knot projections
Report No. 93814, Forschungsinstitut für Diskrete Mathematik, Bonn 1993 (with O.T.Dasbach)

Extremal uniquely hamiltonian graphs
Report No. 93791, Forschungsinstitut für Diskrete Mathematik, Bonn 1993 (with C.Hundack)

Stefan Hougardy, 2024/02/27