Algorithmische Mathematik
2. Auflage, Springer, Juli 2018
Weitere Informationen
1st Edition, Springer Verlag, 2016
ISBN 978-3-319-39557-9
Informationen auf springer.com
Higher Education Press 2021
ISBN 978-7-04-053786-4
| |
S.
Hougardy, J. Vygen Algorithmische Mathematik 2. Auflage, Springer, Juli 2018 Weitere Informationen |
|
Algorithmic Mathematics 1st Edition, Springer Verlag, 2016 ISBN 978-3-319-39557-9 Informationen auf springer.com |
|
Algorithmic Mathematics Higher Education Press 2021 ISBN 978-7-04-053786-4 |
| [63] |
Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching Proceedings of the 22nd International Workshop on Approximation and Online Algorithms (WAOA 2024), 2024 (with Karolina Tammemaa) |
| [62] |
The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5 Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024), 2024, 84:1-84:18 (with Sophia Heimann, Hung P. Hoang) |
| [61] |
The Bottom-Left Algorithm for the Strip Packing Problem Combinatorial Algorithms, IWOCA 2024, LNCS 14764, 433-445 (with Bart Zondervan) |
| [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 ) |
| [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 |
| 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) |