@conference{KottlerKaufmann2011, author = "Stephan Kottler and Michael Kaufmann", booktitle = "Pragmatics of SAT", keywords = "multi-core, SAT, parallel", title = " {SA}r{T}agnan - {A} parallel portfolio {SAT} solver with lockless physical clause sharing", year = "2011", } @conference{MW2010, author = "Morteza Monemizadeh and David P. Woodruff", booktitle = "SODA", pages = "1143-1160", title = "1-{P}ass {R}elative-{E}rror {L}_p-{S}ampling with {A}pplications", year = "2010", } @conference{KarrenbauerRothvoss-3-2-Approximation09, author = "A. Karrenbauer and T. Rothvo{\ss}", abstract = "We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k it yields solutions with at most (3/2 + 1/k)*OPT+9k many processors, thus it gives an asymptotic 3/2-approximation algorithm. This improves over the previously best known ratio of 7/4. Our algorithm can be implemented to run in time O(n^2), where n is the number of tasks. It is based on custom-tailored weights for the tasks such that a greedy maximal matching and subsequent partitioning by a first-fit strategy yields the result.", booktitle = "Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA 2010)", keywords = "scheduling; approximation algorithms", pages = "166-177", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{A} 3/2-{A}pproximation {A}lgorithm for {R}ate-{M}onotonic {M}ultiprocessor {S}cheduling of {I}mplicit-{D}eadline {T}asks", volume = "6534", year = "2011", } @conference{N2, author = "Christoph Buchheim and Frauke Liers and Marcus Oswald", booktitle = "WEA 2008: Workshop on Experimental Algorithms", pages = "249-262", series = "LNCS", title = "{A} {B}asic {T}oolbox for {C}onstrained {Q}uadratic 0/1 {O}ptimization", url = "http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zaik2007-561", volume = "5038", year = "2008", } @incollection{SchKra09, author = "A. Sch{\"o}bel and A. Kratz", booktitle = "Robust and Online Large-Scale Optimization", number = "5868", pages = "119-144", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{A} bicriteria approach for robust timetabling", year = "2009", } @article{DBLP:journals/disopt/BuchheimCEGJKMW08, author = "Christoph Buchheim and Markus Chimani and Dietmar Ebner and Carsten Gutwenger and Gunnar W. Klau and Petra Mutzel and Ren{\'e} Weiskircher and Michael J{\"u}nger", journal = "Discrete Optimization", number = "2", pages = "373-388", title = "{A} branch-and-cut approach to the crossing number problem", volume = "5", year = "2008", } @conference{mel:CoughlanLuebbeckeSchulz:10, author = "Eamonn T. Coughlan and Marco E. L{\"u}bbecke and Jens Schulz", address = "Berlin", booktitle = "Proceedings of the 9th International Symposium on Experimental Algorithms (SEA)", pages = "226--238", publisher = "Springer-Verlag", series = "Lect. Notes Comput. Sci.", title = "{A} {B}ranch-and-{P}rice {A}lgorithm for {M}ulti-{M}ode {R}esource {L}eveling", volume = "6049", year = "2010", } @conference{GehweilerM10distributed, author = "Joachim Gehweiler and Henning Meyerhenke", booktitle = "Proc. 7th High-Performance Grid Computing Workshop (HGCW'10) in conjunction with 24th Intl. Parallel and Distributed Processing Symposium (IPDPS'10)", publisher = "IEEE Computer Society", title = "{A} {D}istributed {D}iffusive {H}euristic for {C}lustering a {V}irtual {P}2{P} {S}upercomputer", year = "2010", } @techreport{gs-agdcr-09, author = "Robert G{\"o}rke and Christian Staudt", institution = "ITI Wagner, Department of Informatics, Universit{\"a}t Karlsruhe", note = "Informatik, Uni Karlsruhe, TR 2009-7", title = "{A} {G}enerator for {D}ynamic {C}lustered {R}andom {G}raphs", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000012167", year = "2009", } @techreport{TR08-01-003, author = "Mario Albrecht and Andreas Kerren and Karsten Klein and Oliver Kohlbacher and Petra Mutzel and Wolfgang Paul and Falk Schreiber and Michael Wybrow", institution = "Technische Universit{\"a}t Dortmund", title = "{A} graph-drawing perspective to some open problems in molecular biology", year = "2008", } @conference{DBLP:conf/esa/ChimaniMB08, author = "Markus Chimani and Petra Mutzel and Immanuel M. Bomze", booktitle = "ESA", crossref = "DBLP:conf/esa/2008", pages = "284-296", title = "{A} {N}ew {A}pproach to {E}xact {C}rossing {M}inimization", year = "2008", } @conference{KottlerKaufmannSinz2008a, author = "Stephan Kottler and Michael Kaufmann and Carsten Sinz", booktitle = "Theory and Applications of Satisfiability Testing ", keywords = "SAT ", title = "{A} {N}ew {B}ound for an {NP}-{H}ard {S}ubclass of 3-{SAT} {U}sing {B}ackdoors", url = "http://www.springerlink.com/content/v82v617444665h87", year = "2008", } @article{MeyerhenkeMS09new, author = "Henning Meyerhenke and Burkhard Monien and Thomas Sauerwald", issn = "0743-7315", journal = "Journal of Parallel and Distributed Computing", keywords = "Graph partitioning", note = "Best Paper Awards and Panel Summary: 22nd International Parallel and Distributed Processing Symposium (IPDPS 2008)", number = "9", pages = "750--761", title = "{A} {N}ew {D}iffusion-based {M}ultilevel {A}lgorithm for {C}omputing {G}raph {P}artitions", url = "http://dx.doi.org/10.1016/j.jpdc.2009.04.005", volume = "69", year = "2009", } @conference{MeyerhenkeMonienSauerwald08new, author = "Henning Meyerhenke and Burkhard Monien and Thomas Sauerwald", booktitle = "Proc. 22nd International Parallel and Distributed Processing Symposium, (IPDPS'08)", note = "Best Algorithms Paper Award.", publisher = "IEEE Computer Society", title = "{A} {N}ew {D}iffusion-based {M}ultilevel {A}lgorithm for {C}omputing {G}raph {P}artitions of {V}ery {H}igh {Q}uality", year = "2008", } @article{GnewuchWW12, author = "Michael Gnewuch and Magnus Wahlstr{\"o}m and Carola Winzen", journal = "SIAM J. Numerical Analysis", number = "2", pages = "781-807", title = "{A} {N}ew {R}andomized {A}lgorithm to {A}pproximate the {S}tar {D}iscrepancy {B}ased on {T}hreshold {A}ccepting", volume = "50", year = "2012", } @article{HoltgreweRabema, author = "Manuel Holtgrewe and Anne-Katrin Emde and David Weese and Knut Reinert", abstract = "Background Second generation sequencing technologies yield DNA sequence data at ultra high-throughput. Common to most biological applications is a mapping of the reads to an almost identical or highly similar reference genome. The assessment of the quality of read mapping results is not straightforward and has not been formalized so far. Hence, it has not been easy to compare different read mapping approaches in a unified way and to determine which program is the best for what task. Results We present a new benchmark method, called Rabema (Read Alignment BEnchMArk), for read mappers. It consists of a strict definition of the read mapping problem and of tools to evaluate the result of arbitrary read mappers supporting the SAM output format. Conclusions We show the usefulness of the benchmark program by performing a comparison of popular read mappers. The tools supporting the benchmark are licensed under the GPL and available from http://www.seqan.de/projects/rabema.html.", doi = "10.1186/1471-2105-12-210", journal = "BMC Bioinformatics", keywords = "benchmarks; experiments; read mapping", month = "May", number = "210", title = "{A} {N}ovel {A}nd {W}ell-{D}efined {B}enchmarking {M}ethod {F}or {S}econd {G}eneration {R}ead {M}apping", url = "http://www.biomedcentral.com/1471-2105/12/210", volume = "12", year = "2011", } @conference{PPS09, author = "C. Patvardhan and Prem Prakash and Anand Srivastav", booktitle = "Proceedings of the International Conference on Operations Research Applications In Engineering And Management, Tiruchirappalli, India, May 2009 (ICOREM 2009)", note = "Best OR Application in Engineering Award, sponsored by the Anna University, Tiruchirappalli", pages = "2061-2064", title = "{A} {N}ovel {Q}uantum-inspired {E}volutionary {A}lgorithm for the {Q}uadratic {K}napsack {P}roblem", year = "2009", } @conference{FeldmanMonemizadehSohler2007, author = "Dan Feldman and Morteza Monemizadeh and Christian Sohler", booktitle = "Proceedings of the 23th annual symposium on Computational geometry, SoCG 2007", pages = "11--18", title = "{A} {PTAS} for k-means clustering based on weak coresets", year = "2007", } @conference{static-priority-PTAS, author = "Friedrich Eisenbrand and Thomas Rothvo{\ss}", booktitle = "35th international Colloquium on Automata, Languages and Programming (ICALP 2008)", pages = "246--257", publisher = "Springer", title = "{A} {PTAS} for static priority real-time scheduling with resource augmentation", url = "http://www.springerlink.com/content/p67741581859k617/", year = "2008", } @conference{TAPAS2011-goerigk, author = "Marc Goerigk and Anita Sch{\"o}bel", abstract = "Finding robust solutions of an optimization problem is an important issue in practice. The established concept of Ben-Tal et al. requires that a robust solution is feasible for all possible scenarios. However, this concept is very conservative and hence may lead to solutions with a bad objective value and is in many cases hard to solve. Thus it is not suitable for most practical applications. In this paper we suggest an algorithm for calculating robust solutions that is easy to implement and not as conservative as the strict robustness approach. We show some theoretical properties of our approach and evaluate it using linear programming problems from NetLib? .", booktitle = "The 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS)", note = "to appear", series = "LNCS", title = "{A} {S}cenario-{B}ased {A}pproach for {R}obust {L}inear {O}ptimization", year = "2011", } @conference{CH11, author = "Markus Chimani and Petr Hliněn{\'y}", booktitle = "International Colloquium on Automata, Languages and Programming (ICALP11)", pages = "122-134", title = "{A} {T}ighter {I}nsertion-based {A}pproximation of the {C}rossing {N}umber", year = "2011", } @conference{berger_et_al:DSP:2009:2148, author = "Annabell Berger and Daniel Delling and Andreas Gebhardt and Matthias M{\"u}ller-Hannemann", address = "Dagstuhl, Germany", booktitle = "ATMOS 2009 - 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems", editor = "Jens Clausen and Gabriele Di Stefano", isbn = "9783939897118", publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Germany", title = "{A}ccelerating {T}ime-{D}ependent {M}ulti-{C}riteria {T}imetable {I}nformation is {H}arder {T}han {E}xpected", url = "http://drops.dagstuhl.de/opus/volltexte/2009/2148", year = "2009", } @conference{San09, author = "Peter Sanders", booktitle = "Efficient Algorithms", pages = "321--340", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{A}lgorithm {E}ngineering -- {A}n {A}ttempt at a {D}efinition", url = "http://algo2.iti.kit.edu/1577.php", volume = "5760", year = "2009", } @proceedings{Mueller-HannemannSchirra10, author = "", editor = "Matthias M{\"u}ller-Hannemann and Steffen Schirra", publisher = "Springer, Heidelberg", series = "LNCS", title = "{A}lgorithm {E}ngineering --- {B}ridging the gap between algorithm theory and practice", volume = "5971", year = "2010", } @mastersthesis{GraphDrawing18, author = "Thorsten Kerkhof", note = "Diplomarbeit", title = "{A}lgorithmen zur {B}estimmung von guten {G}raph-{E}inbettungen f{\"u}r orthogonale {Z}eichnungen", year = "2007", } @article{Doerr2010, author = "Benjamin Doerr and Michael Gnewuch and Magnus Wahlstr{\"o}m", doi = "DOI: 10.1016/j.jco.2010.03.004", issn = "0885-064X", journal = "Journal of Complexity", number = "5", pages = "490-507", title = "{A}lgorithmic construction of low-discrepancy point sets via dependent randomized rounding", url = "http://www.sciencedirect.com/science/article/B6WHX-4YT6D3V-1/2/a75b2b4c235f5e0d1d40eca084e2b4aa", volume = "26", year = "2010", } @mastersthesis{mel:Bastubbe:11, author = "Michael Bastubbe", school = "Technische Universit{\"a}t Berlin", title = "{A}lgorithms for {D}etecting {B}lock {S}tructures in {M}atrices", type = "Diplomarbeit", year = "2011", } @mastersthesis{GraphDrawing16, author = "Bernd T. Zey", note = "Diplomarbeit", title = "{A}lgorithms for {P}lanar {G}raph {A}ugmentation", year = "2008", } @phdthesis{Ackermann2009, author = "Marcel R. Ackermann", publisher = "Dissertation, University of Paderborn, Department of Compute", title = "{A}lgorithms for the {B}regman k-{M}edian {P}roblem", year = "2010", } @conference{DBLP:conf/isaac/ChimaniG07, author = "Markus Chimani and Carsten Gutwenger", booktitle = "ISAAC", crossref = "DBLP:conf/isaac/2007", pages = "184-195", title = "{A}lgorithms for the {H}ypergraph and the {M}inor {C}rossing {N}umber{P}roblems", year = "2007", } @phdthesis{g-aawsd-10, author = "Robert G{\"o}rke", institution = "Karlsruhe Institute of Technology (KIT)", month = "February", school = "Department of Informatics", title = "{A}n {A}lgorithmic {W}alk from {S}tatic to {D}ynamic {G}raph {C}lustering", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000018288", year = "2010", } @conference{rate-monotonic-multiprocessor, author = "Andreas Karrenbauer and Thomas Rothvo{\ss}", booktitle = "17th Annual European Symposium on Algorithms (ESA 2009)", pages = "432--443", series = "LNCS", title = "{A}n {A}verage-{C}ase {A}nalysis for {R}ate-{M}onotonic {M}ultiprocessor {R}eal-time {S}cheduling", url = "http://www.springerlink.com/content/bq200377t3x21500/", volume = "5757", year = "2009", } @conference{Atmos2010-goerigk, author = "Marc Goerigk and Anita Sch{\"o}bel", abstract = "Calculating timetables that are insensitive to disturbances has drawn considerable research efforts due to its practical importance on the one hand and its hard tractability by classical robustness concepts on the other hand. Many different robustness concepts for timetabling have been suggested in the literature, some of them very recently. In this paper we compare such concepts on real-world instances. We also introduce a new approach that is generically applicable to any robustness problem. Nevertheless it is able to adapt the special characteristics of the respective problem structure and hence generates solutions that fit to the needs of the respective problem.", address = "Dagstuhl, Germany", booktitle = "Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems", editor = "Thomas Erlebach and Marco L{\"u}bbecke", isbn = "978-3-939897-20-0", issn = "2190-6807", pages = "100--113", publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik", series = "OpenAccess Series in Informatics (OASIcs)", title = "{A}n {E}mpirical {A}nalysis of {R}obustness {C}oncepts for {T}imetabling", url = "http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.100", volume = "14", year = "2010", } @conference{CookKochStefWolt11, author = "William Cook and Thorsten Koch and Daniel E. Steffy and Kati Wolter", booktitle = "IPCO 2011: Proceedings of the 15th International Conference on Integer Programming and Combinatoral Optimization", editor = "Oktay G{\"u}nl{\"u}k, Gerhard J. Woeginger", institution = "Zuse Institute Berlin", pages = "104-116", series = "Lecture Notes in Computer Science", title = "{A}n {E}xact {R}ational {M}ixed-{I}nteger {P}rogramming {S}olver", type = "ZIB-Report", url = "http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1232", volume = "6655", year = "2011", } @conference{HoeJa12a, author = "Wiebke H{\"o}hn and Tobias Jacobs", abstract = "We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances.", booktitle = "Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX)", pages = "103-117", publisher = "SIAM", title = "{A}n experimental and analytical study of order constraints for single machine scheduling with quadratic cost", year = "2012", } @conference{DBLP:conf/gd/BartelGKM10, author = "Carsten Gutwenger and Karsten Klein and Petra Mutzel and Gereon Bartel", booktitle = "Graph Drawing", editor = "U. Brandes and S. Cornelsen", pages = "80-91", publisher = "Springer", series = "LNCS", title = "{A}n {E}xperimental {E}valuation of {M}ultilevel {L}ayout {M}ethods", volume = "6502", year = "2010", } @article{Chimani2012a_1, author = "Markus Chimani and Philipp Hungerlaender and Michael Juenger and Petra Mutzel", journal = "ACM Journal of Experimental Algorithmics", note = "to appear", title = "{A}n {SDP} {A}pproach to {M}ulti-level {C}rossing {M}inimization", year = "2012", } @article{Ch_Hu_Ju_Mu, author = "Markus Chimani and Philipp Hungerl{\"a}nder and Michael J{\"u}nger and Petra Mutzel", journal = "Workshop on Algorithm Engineering and Experiments 2011 (ALENEX11)", title = "{A}n {SDP} {A}pproach to {M}ulti-level {C}rossing {M}inimization", year = "2011", } @conference{1506897, author = "Carsten Gutwenger and Michael J{\"u}nger and Petra Mutzel and Michael Schulz and Joseph J. Fowler", address = "Berlin, Heidelberg", pages = "157--168", publisher = "Springer-Verlag", title = "{A}n {SPQR}-{T}ree {A}pproach to {D}ecide {S}pecial {C}ases of {S}imultaneous {E}mbedding with {F}ixed {E}dges", url = "http://dx.doi.org/10.1007/978-3-642-00219-9_16", year = "2009", } @mastersthesis{Dau2010, author = "Andre Dau", note = "Bachelor thesis", organization = "Technische Universit{\"a}t M{\"u}nchen", school = "Technische Universit{\"a}t M{\"u}nchen", title = "{A}nalyse der {S}truktur und statistischer {E}igenschaften von {T}exten und {E}rzeugung zuf{\"a}lliger {T}exte", url = "http://www14.in.tum.de/diplomarbeiten/abgeschlossen/2010-dau.pdf", year = "2010", } @conference{abks11, author = "Marcel R. Ackermann and Johannes Bl{\"o}mer and Daniel Kuntze and Christian Sohler", booktitle = "28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011", pages = "308-319", title = "{A}nalysis of {A}gglomerative {C}lustering", year = "2011", } @article{Doncheva2011, author = "Nadezhda T. Doncheva and Karsten Klein and Francisco S. Domingues and Mario Albrecht", doi = "10.1016/j.tibs.2011.01.002", issn = "0968-0004", journal = "Trends in Biochemical Sciences", number = "4", pages = "179 - 182", title = "{A}nalyzing and visualizing residue networks of protein structures", url = "http://www.sciencedirect.com/science/article/pii/S0968000411000132", volume = "36", year = "2011", } @phdthesis{Gutwenger10, author = "Carsten Gutwenger", school = "Fakult{\"a}t f{\"u}r Informatik, Technische Universit{\"a}t Dortmund", title = "{A}pplication of {SPQR}-trees in the planarization approach for drawing graphs", year = "2010", } @conference{1506924, author = "Markus Chimani and Petr Hliněn{\'y} and Petra Mutzel", address = "Berlin, Heidelberg", booktitle = "Graph Drawing", doi = "http://dx.doi.org/10.1007/978-3-642-00219-9_42", pages = "432--434", publisher = "Springer-Verlag", title = "{A}pproximating the {C}rossing {N}umber of {A}pex {G}raphs", year = "2009", } @mastersthesis{Poppe2010, author = "Henrik Poppe", note = "Bachelor thesis", school = "Technische Universit{\"a}t M{\"u}nchen", title = "{A}pproximative {S}uche in {T}extindizes", url = "http://www14.in.tum.de/diplomarbeiten/abgeschlossen/2010-poppe.pdf", year = "2010", } @conference{DoerrF11, author = "Benjamin Doerr and Mahmoud Fouz", booktitle = "ICALP", note = "To appear.", title = "{A}symptotically {O}ptimal {R}andomized {R}umor {S}preading", year = "2011", } @conference{DoerrFF12b, author = "Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich", booktitle = "SWAT", crossref = "DBLP:conf/swat/2012", pages = "307-315", title = "{A}synchronous {R}umor {S}preading in {P}referential {A}ttachment {G}raphs", year = "2012", } @conference{mel:Luebbecke:12, author = "Marco E. L{\"u}bbecke", address = "Berlin", booktitle = "Experimental Algorithms", editor = "R. Klasing", pages = "1-8", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{A}utomatic decomposition and branch-and-price: {A} status report", volume = "7276", year = "2012", } @mastersthesis{GraphDrawing14, author = "Sven Mallach", note = "Diplomarbeit", title = "{B}eschleunigung ausgew{\"a}hlter paralleler {S}tandard {T}emplate {L}ibrary {A}lgorithmen", year = "2008", } @conference{Meyerhenke10beyond, author = "Henning Meyerhenke", booktitle = "Proc. 21st International Symposium on Algorithms and Computation (ISAAC'10)", note = "To appear", publisher = "Springer-Verlag", title = "{B}eyond {G}ood {S}hapes: {D}iffusion-based {G}raph {P}artitioning is {R}elaxed {C}ut {O}ptimization", year = "2010", } @conference{KaufmannKottler2011, author = "Michael Kaufmann and Stephan Kottler", booktitle = "Symposium on Experimental Algorithms", keywords = "SAT, Boolean Constraint Propagation, Reasoning", title = "{B}eyond {U}nit {P}ropagation in {SAT} {S}olving", url = "http://www.springerlink.com/content/fp32471340gxm242", year = "2011", } @conference{EggKliSri09, author = "Sebastian Eggert and Lasse Kliemann and Anand Srivastav", booktitle = "Proceedings of the 17th Annual European Symposium on Algorithms (ESA)", note = "Presented also at the MADALGO Workshop on Massive Data Algorithmics, June 2009, rArhus, Denmark", pages = "492--503", title = "{B}ipartite {G}raph {M}atchings in the {S}emi-{S}treaming {M}odel", url = "http://dx.doi.org/10.1007/978-3-642-04128-0_44", year = "2009", } @article{EKMS11, author = "Sebastian Eggert and Lasse Kliemann and Peter Munstermann and Anand Srivastav", doi = "10.1007/s00453-011-9556-8", journal = "Algorithmica", note = "Document ID: 519a88bb-5f5a-409d-8293-13cd80a66b36. Conference version in proceedings of ESA 2009.", number = "1-2", pages = "490-508", title = "{B}ipartite {M}atching in the {S}emi-{S}treaming {M}odel", volume = "63", year = "2011", } @incollection{mel:DesrosiersLuebbecke:11, author = "Jacques Desrosiers and Marco E. L{\"u}bbecke", address = "Chichester", booktitle = "Encyclopedia of Operations Research and Management Science", editor = "J.J. Cochran", publisher = "John Wiley {\&} Sons", title = "{B}ranch-{P}rice-and-{C}ut {A}lgorithms", year = "2011", } @conference{Ajwani09DM, author = "Deepak Ajwani and Roman Dementiev and Ulrich Meyer", booktitle = "Shortest Path Computations: Ninth DIMACS Challenge", isbn = "978-0-8218-4383-3", pages = "291-307", publisher = "American Mathematical Society", series = "DIMACS Series on Disrecte Mathematics and Theoretical Computer Scienc", title = "{B}readth first search on massive graphs", volume = "74", year = "2009", } @conference{AckermannBlomer2010, author = "Marcel R. Ackermann and Johannes Bl{\"o}mer", booktitle = "Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory, SWAT 2010", pages = "212--223", publisher = "Springer", title = "{B}regman {C}lustering for {S}eparable {I}nstances", year = "2010", } @conference{BeckmannDS09, author = "Andreas Beckmann and Roman Dementiev and Johannes Singler", booktitle = "23rd IEEE International Symposium on Parallel and Distributed Processing", crossref = "DBLP:conf/ipps/2009", doi = "http://dx.doi.org/10.1109/IPDPS.2009.5161001", pages = "1-10", publisher = "IEEE", title = "{B}uilding {A} {P}arallel {P}ipelined {E}xternal {M}emory {A}lgorithm {L}ibrary", year = "2009", } @conference{ParallelStxxlIpdps2009, author = "Andreas Beckmann and Roman Dementiev and Johannes Singler", address = " ", booktitle = "23rd IEEE International Parallel {{\&}} Distributed Processing Symposium (IPDPS)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = " ", publisher = " ", series = " ", title = "{B}uilding {A} {P}arallel {P}ipelined {E}xternal {M}emory {A}lgorithm {L}ibrary", url = "http://dx.doi.org/10.1109/IPDPS.2009.5161001", volume = " ", year = "2009", } @conference{BeckmannDS09_1, author = "Andreas Beckmann and Roman Dementiev and Johannes Singler", booktitle = "23rd IEEE International Symposium on Parallel and Distributed Processing", crossref = "DBLP:conf/ipps/2009", doi = "http://dx.doi.org/10.1109/IPDPS.2009.5161001", pages = "1-10", publisher = "IEEE", title = "{B}uilding {A} {P}arallel {P}ipelined {E}xternal {M}emory {A}lgorithm {L}ibrary_1", year = "2009", } @article{CacheBloomFiltersJEA2009, author = "Felix Putze and Peter Sanders and Johannes Singler", crossref = " ", journal = "ACM Journal of Experimental Algorithmics", month = " ", number = " ", pages = "4.4-4.18", title = "{C}ache-, {H}ash- and {S}pace-{E}fficient {B}loom {F}ilters", url = "http://doi.acm.org/10.1145/1498698.1594230", volume = "14", year = "2009", } @conference{CacheBloomFiltersWea2007, author = "Felix Putze and Peter Sanders and Johannes Singler", address = " ", booktitle = "6th Workshop on Experimental Algorithms (WEA)", crossref = " ", editor = " ", month = " ", number = "4525", organization = " ", pages = "108-121", publisher = "Springer-Verlag", series = "LNCS", title = "{C}ache-, {H}ash- and {S}pace-{E}fficient {B}loom {F}ilters", url = "http://dx.doi.org/10.1007/978-3-540-72845-0_9", volume = " ", year = "2007", } @article{Fowler2011, author = "J. Joseph Fowler and Michael J{\"u}nger and Stephen G. Kobourov and Michael Schulz", journal = "Comput. Geom.", number = "8", pages = "385-398", title = "{C}haracterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges", volume = "44", year = "2011", } @conference{DBLP:conf/wg/FowlerJKS08, author = "Michael J{\"u}nger and Stephen G. Kobourov and Michael Schulz and Joseph J. Fowler", booktitle = "WG", crossref = "DBLP:conf/wg/2008", pages = "146-158", title = "{C}haracterizations of {R}estricted {P}airs of {P}lanar {G}raphs {A}llowing {S}imultaneous {E}mbedding with {F}ixed {E}dges", year = "2008", } @article{DBLP:journals/endm/FowlerJKS08, author = "Michael J{\"u}nger and Stephen G. Kobourov and Michael Schulz and Joseph J. Fowler", journal = "Electronic Notes in Discrete Mathematics", pages = "41-44", title = "{C}haracterizing {S}imultaneous {E}mbedding with {F}ixed {E}dges", volume = "31", year = "2008", } @conference{AjwaniMMT08, author = "Deepak Ajwani and Itay Malinger and Ulrich Meyer and Sivan Toledo", booktitle = "7th International Workshop on Experimental Algorithms", crossref = "DBLP:conf/wea/2008", doi = "http://dx.doi.org/10.1007/978-3-540-68552-4_16", isbn = "978-3-540-68548-7", pages = "208-219", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{C}haracterizing the {P}erformance of {F}lash {M}emory {S}torage {D}evices ", volume = "5038", year = "2008", } @mastersthesis{h-cdggq-08, author = "Tanja Hartmann", institution = "Universit{\"a}t Karlsruhe (TH)", month = "October", note = "Diplomarbeit", school = "Department of Informatics", title = "{C}lustering {D}ynamic {G}raphs with {G}uaranteed {Q}uality", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#diplomarbeiten_master_s_theses", year = "2008", } @article{AckermannBlomerSohler2010, author = "Marcel R. Ackermann and Johannes Bl{\"o}mer and Christian Sohler", journal = "ACM Transactions on Algorithms", month = "August", number = "4", pages = "59:1--26", title = "{C}lustering for {M}etric and {N}on-{M}etric {D}istance {M}easures", volume = "6", year = "2010", } @conference{DBLP:conf/cocoon/BrandesEFFGGHKKLMS07, author = "Ulrik Brandes and Cesim Erten and Fabrizio Frati and Markus Geyer and Carsten Gutwenger and Seok-Hee Hong and Michael Kaufmann and Stephen G. Kobourov and Giuseppe Liotta and Petra Mutzel and Antonios Symvonis and Joseph J. Fowler", booktitle = "COCOON", crossref = "DBLP:conf/cocoon/2007", pages = "254-263", title = "{C}olored {S}imultaneous {G}eometric {E}mbeddings", year = "2007", } @article{BEFFGGHKKLMS10, author = "Cesim Erten and Fabrizio Frati and Markus Geyer and Carsten Gutwenger and Seok-Hee Hong and Michael Kaufmann and Stephen G. Kobourov and Giuseppe Liotta and Petra Mutzel and Antonios Symvonis and Ulrik Brandes and Alejandro Estrella-Balderrama and Joseph J. Fowler", journal = "Algorithmica", number = "60", pages = "569-592", title = "{C}olored {S}imultaneous {G}eometric {E}mbeddings and {U}niversal {P}ointsets", volume = "3", year = "2011", } @incollection{mel:Luebbecke:11, author = "Marco E. L{\"u}bbecke", address = "Chichester", booktitle = "Encyclopedia of Operations Research and Management Science", editor = "J.J. Cochran", publisher = "John Wiley {\&} Sons", title = "{C}olumn {G}eneration", year = "2011", } @techreport{ww-ccao-07, author = "Silke Wagner and Dorothea Wagner", institution = "Universit{\"a}t Karlsruhe (TH)", number = "2006-04", school = "Department of Informatics", title = "{C}omparing {C}lusterings -- {A}n {O}verview", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000011477", year = "2007", } @article{DGKP08, author = "Benjamin Doerr and Michael Gnewuch and Peter Kritzer and Friedrich Pillichshammer", isbn = "0929-9629", journal = "Monte Carlo Methods and Applications", pages = "129--149", title = "{C}omponent-by-component construction of low-discrepancy point sets of small size", volume = "14", year = "2008", } @conference{KottlerKaufmannSinz2008, author = "Stephan Kottler and Michael Kaufmann and Carsten Sinz", booktitle = "Theory and Applications of Satisfiability Testing", keywords = "SAT, Backdoors, Horn", title = "{C}omputation of {R}enameable {H}orn {B}ackdoors", url = "http://www.springerlink.com/content/l7234h5900qnt178", year = "2008", } @article{gghw-caldg-10, author = "Robert G{\"o}rke and Marco Gaertler and Florian H{\"u}bner and Dorothea Wagner", journal = "Journal of Graph Algorithms and Applications", month = "January", number = "2", pages = "165--197", title = "{C}omputational {A}spects of {L}ucidity-{D}riven {G}raph {C}lustering", url = "http://www.cs.brown.edu/sites/jgaa/volume14.html", volume = "14", year = "2010", } @conference{mghemc-c-10, author = "Anke Meyer-B{\"a}se and Robert G{\"o}rke and Huan He and Mark R. Emmett and Alan G. Marshall and Charles A. Conrad", booktitle = "Proceedings of SPIE 7704: Evolutionary and Bio-Inspired Computation: Theory and Applications IV (2010)", month = "April", publisher = "SPIE--The International Society for Optical Engineering", title = "{C}omputational techniques to the topology and dynamics of lipidomic networks found in glioblastoma cells", url = "http://dx.doi.org/10.1117/12.849903", year = "2010", } @conference{DBLP:conf/gd/ChimaniGJKM08, author = "Markus Chimani and Carsten Gutwenger and Mathias Jansen and Karsten Klein and Petra Mutzel", booktitle = "Graph Drawing", crossref = "DBLP:conf/gd/2008", pages = "114-120", title = "{C}omputing {M}aximum {C}-{P}lanar {S}ubgraphs", year = "2008", } @phdthesis{GraphDrawing11, author = "Merijam Percan", school = "Universit{\"a}t zu K{\"o}ln", title = "{C}onstrained {P}lanarity and {A}ugmentation {P}roblems", year = "2007", } @conference{AchtBertKochWolt08, author = "Tobias Achterberg and Timo Berthold and Thorsten Koch and Kati Wolter", booktitle = "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008", editor = "Laurent Perron and Michael A. Trick", pages = "6--20", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{C}onstraint {I}nteger {P}rogramming: {A} {N}ew {A}pproach to {I}ntegrate {CP} and {MIP}", volume = "5015", year = "2008", } @conference{Tristan2010-schoebel, author = "A. Sch{\"o}bel", address = "Tromso, Norway", booktitle = "Proceedings of the TRISTAN VII conference", editor = "G. Hasle", month = "June", pages = "689-693", title = "{C}ontrolling the level of robustness in timetabling and scheduling: {A} bicriterias approach", year = "2010", } @conference{AB09, author = "Marcel R. Ackermann and Johannes Bl{\"o}mer", booktitle = "SODA 2009", pages = "1088--1097", publisher = "SIAM: Society for Industrial and Applied Mathematics", title = "{C}oresets and {A}pproximate {C}lustering for {B}regman {D}ivergences", year = "2009", } @conference{FMSW10, author = "Dan Feldman and Morteza Monemizadeh and Christian Sohler and David P. Woodruff", booktitle = "Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010", pages = "630--649", publisher = "SIAM: Society for Industrial and Applied Mathematics", title = "{C}oresets and sketches for high dimensional subspace approximation problems", year = "2010", } @conference{BrodalJMM09, author = "Gerth Stolting Brodal and Allan Gronlund Jorgensen and Gabriel Moruz and Thomas Molhave", booktitle = "Proc. 20th International Symposium on Algorithms and Computation", crossref = "DBLP:conf/isaac/2009", pages = "842-851", title = "{C}ounting in the {P}resence of {M}emory {F}aults", year = "2009", } @conference{GraphDrawing3, author = "Markus Chimani and Carsten Gutwenger and Petra Mutzel and Miro Spoenemann and Hoi-Ming Wong", booktitle = "Graph Drawing", note = "to appear", title = "{C}rossing {M}inimization and {L}ayouts of {D}irected {H}ypergraphs with {P}ort {C}onstraints", year = "2010", } @conference{DBLP:conf/apvis/ChimaniJS08, author = "Markus Chimani and Michael J{\"u}nger and Michael Schulz", booktitle = "PacificVis", crossref = "DBLP:conf/apvis/2008", pages = "33-40", title = "{C}rossing {M}inimization meets {S}imultaneous {D}rawing", year = "2008", } @inbook{ChristophBuchheim2012, author = "Christoph Buchheim and Markus Chimani and Carsten Gutwenger and Michael J{\"u}nger and Petra Mutzel", booktitle = "Handbook of Graph Drawing and Visualization", editor = "R. Tamassia", note = "to appear", publisher = "CRC Press", title = "{C}rossings and {P}lanarization", year = "2012", } @conference{KKM, author = "Karsten Klein and Nils Kriege and Petra Mutzel", booktitle = "International Conference on Data Engineering (ICDE)", pages = "1115-1126", title = "{CT}-{I}ndex: {F}ingerprint-based graph indexing combining cycles and trees", year = "2011", } @misc{GraphDrawing4, author = "Stephen P. Borgatti and Stephen G. Kobourov and Oliver Kohlbacher and Petra Mutzel", title = "{D}agstuhl {S}eminar 08191: {G}raph {D}rawing", year = "2008", } @mastersthesis{Knoll2012, author = "Christian Knoll", school = "Universit{\"a}t zu K{\"o}ln", title = "{D}as bin{\"a}re {S}tressmodell - {M}ethoden der {N}achbearbeitung", year = "2012", } @article{MeMoeSch11, author = "Nicole Megow and Rolf H. M{\"o}hring and Jens Schulz", abstract = "This paper concerns the highly complex task of scheduling large-scale maintenance activities during a plants shutdown or turnaround. We model it as a discrete time-cost tradeoff problem with capacity constraints and individual working shifts for different resource types with a cost function regarding a balanced resource consumption. We introduce and model the problem, give an overview on the large variety of related optimization problems, and propose a framework for supporting managers decisions in the planning process of such an event. Our key component is an optimization algorithm complemented with a risk analysis of solutions. We implemented a two-phase solution method in which we first provide an approximation of the tradeoff between project duration and cost as well as a stochastic evaluation of the risk for meeting the makespan. In a second, detailed planning phase, we solve the actual scheduling optimization problem for a chosen deadline heuristically and compute a detailed schedule that we complement by evaluating upper bounds for the two risk measures expected tardiness and the probability of meeting the deadline. We present experimental results showing that our methods can handle large real-world instances within seconds and yield a leveled resource consumption. For smaller instances a comparison with solutions of a time-consuming mixed integer program prove the high quality of the solutions that our fast heuristic produces.", journal = "INFORMS Journal on Computing", pages = "189-204", title = "{D}ecision {S}upport and {O}ptimization in {S}hutdown and {T}urnaround {S}cheduling", url = "http://www.math.tu-berlin.de/coga/publications/techreports/2009/Report-009-2009.xhtml", volume = "23", year = "2011", } @article{BJMM-2012, author = "Anja Becker and Antoine Joux and Alexander May and Alexander Meurer", journal = "Advances in Cryptology -- EUROCRYPT 2012, LNCS", title = "{D}ecoding {R}andom {B}inary {L}inear {C}odes in 2^(n/20): {H}ow 1+1=0 {I}mproves {I}nformation {S}et {D}ecoding", year = "2012", } @article{MMT2011, author = "Alexander May and Alexander Meurer and Enrico Thomae", journal = "Advances in Cryptology -- ASIACRYPT 2011, Springer LNCS", pages = "107-124", title = "{D}ecoding {R}andom {L}inear {C}odes in {O}(2^{0.054n})", url = "http://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/decoding.pdf", volume = "7073", year = "2011", } @conference{DKW11, author = "Benjamin Doerr and Marvin K{\"u}nnemann and Magnus Wahlstr{\"o}m", booktitle = "ALENEX", pages = "96-106", title = "{D}ependent {R}andomized {R}ounding: {T}he {B}ipartite {C}ase", year = "2011", } @conference{AjwaniM09, author = "Deepak Ajwani and Ulrich Meyer", booktitle = "Algorithmics of Large and Complex Networks", crossref = "DBLP:conf/dfg/2009netw", doi = "http://dx.doi.org/10.1007/978-3-642-02094-0_1", isbn = "978-3-642-02093-3", pages = "1-33", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{D}esign and {E}ngineering of {E}xternal {M}emory {T}raversal {A}lgorithms for {G}eneral {G}raphs", volume = "5515", year = "2009", } @misc{s-deelg-08, author = "Christian Schulz", institution = "Universit{\"a}t Karlsruhe (TH)", month = "June", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{D}esign and {E}xperimental {E}valuation of a {L}ocal {G}raph {C}lustering {A}lgorithm", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#studienarbeiten_student_projects", year = "2008", } @conference{MO09, author = "Ulrich Meyer and Vitaly Osipov", abstract = "We report on initial experimental results for a practical I/O-efficient Single-Source Shortest-Paths (SSSP) algorithm on general undirected sparse graphs where the ratio between the largest and the smallest edge weight is reasonably bounded (for example integer weights in $\{1, \ldots, 2^{32}\}$) and the realistic assumption holds that main memory is big enough to keep one bit per vertex. While our implementation only guarantees average-case efficiency, i.e., assuming randomly chosen edge-weights, it turns out that its performance on real-world instances with non-random edge weights is actually even better than on the respective inputs with random weights. Furthermore, compared to the currently best implementation for external-memory BFS, which in a sense constitutes a lower bound for SSSP, the running time of our approach always stayed within a factor of five, for the most difficult graph classes the difference was even less than a factor of two. We are not aware of any previous I/O-efficient implementation for the classic general SSSP in a (semi) external setting: in two recent projects Kumar/Schwabe-like SSSP approaches on graphs of at most 6 million vertices have been tested, forcing the authors to artificially restrict the main memory size, $M$, to rather unrealistic 4 to 16 MBytes in order not to leave the semi-external setting or produce huge running times for larger graphs: for random graphs of $2^{20}$ vertices, the best previous approach needed over six hours. In contrast, for a similar ratio of input size vs. $M$, but on a 128 times larger and even sparser random graph, our approach was less than seven times slower, a relative gain of nearly 20. On a real-world 24 million node street graph, our implementation was over 40 times faster. Even larger gains of over 500 can be estimated for random line graphs based on previous experimental results for Munagala/Ranade-BFS. Finally, we also report on early results of experiments in which we replace the hard disk by a solid state disk (flash memory). ", address = " ", booktitle = "10th Workshop on Algorithm Engineering and Experiments (ALENEX)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = "85--96", publisher = " ", series = " ", title = "{D}esign and {I}mplementation of a {P}ractical {I}/{O}-efficient {S}hortest {P}aths {A}lgorithm", url = "http://www.siam.org/proceedings/alenex/2009/alx09_009_meyeru.pdf ", volume = " ", year = "2009", } @article{gmwhec-d-10, author = "Robert G{\"o}rke and Anke Meyer-B{\"a}se and Christopher G. Wagner and Huan He and Mark R. Emmett and Charles A. Conrad", journal = "BMC Systems Biology", month = "September", number = "126", title = "{D}etermining and interpreting correlations in lipidomic networks found in glioblastoma cells", url = "http://www.biomedcentral.com/1752-0509/4/126", volume = "4", year = "2010", } @phdthesis{Meyerhenke08disturbed, author = "Henning Meyerhenke", month = "April", school = "Universit{\"a}t Paderborn", title = "{D}isturbed {D}iffusive {P}rocesses for {S}olving {P}artitioning {P}roblems on {G}raphs", year = "2008", } @techreport{Gronemann2012, author = "Martin Gronemann and Michael J{\"u}nger", keywords = "Graph visualization, clustered graphs, topographic maps, edge routing", title = "{D}rawing {C}lustered {G}raphs as {T}opographic {M}aps", url = "http://gdea.informatik.uni-koeln.de/1283/", year = "2012", } @unpublished{gmssw-dgccm-11a, author = "Robert G{\"o}rke and Pascal Maillard and Andrea Schumm and Christian Staudt and Dorothea Wagner", note = "under revision at Journal of Experimental Algorithmics", title = "{D}ynamic {G}raph {C}lustering {C}ombining {M}odularity and {S}moothness", year = "2011", } @techreport{gmssw-dgccm-11, author = "Robert G{\"o}rke and Pascal Maillard and Andrea Schumm and Christian Staudt and Dorothea Wagner", institution = "ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT)", note = "Karlsruhe Reports in Informatics 2011-11 (and invitational submission to a Special Issue of the ACM Journal on Experimental Algorithmics)", title = "{D}ynamic {G}raph {C}lustering {C}ombining {M}odularity and {S}moothness", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000022451", year = "2011", } @conference{ghw-dmctc-09, author = "Robert G{\"o}rke and Tanja Hartmann and Dorothea Wagner", booktitle = "Algorithms and Data Structures, 11th International Workshop (WADS'09)", editor = "Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Roberto Tamassia", month = "August", pages = "339--350", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{D}ynamic {G}raph {C}lustering {U}sing {M}inimum-{C}ut {T}rees", url = "http://dx.doi.org/10.1007/978-3-642-03367-4_30", volume = "5664", year = "2009", } @unpublished{ghw-dcc-11, author = "Robert G{\"o}rke and Tanja Hartmann and Dorothea Wagner", note = "under revision at Journal of Graph Algorithms and Applications", title = "{D}ynamic {G}raph {C}lustering {U}sing {M}inimum-{C}ut {T}rees", year = "2011", } @techreport{ghw-dgcum-11, author = "Robert G{\"o}rke and Tanja Hartmann and Dorothea Wagner", institution = "ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT)", note = "Karlsruhe Reports in Informatics 2011-12 (and under revision at Journal of Graph Algorithms and Applications)", title = "{D}ynamic {G}raph {C}lustering {U}sing {M}inimum-{C}ut {T}rees", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000022477", year = "2011", } @conference{Meyerhenke09dynamic, author = "Henning Meyerhenke", booktitle = "Proc. Internatl. Conference on Parallel and Distributed Systems (ICPADS'09)", issn = "1521-9097", pages = "150-157", publisher = "IEEE Computer Society", title = "{D}ynamic {L}oad {B}alancing for {P}arallel {N}umerical {S}imulations {B}ased on {R}epartitioning with {D}isturbed {D}iffusion", url = "http://doi.ieeecomputersociety.org/10.1109/ICPADS.2009.114", year = "2009", } @mastersthesis{m-dcdmv-09, author = "Selma Mukhtar", institution = "Universit{\"a}t Karlsruhe (TH)", month = "April", note = "Diplomarbeit", school = "Department of Informatics", title = "{D}ynamische {C}lusteranalyse f{\"u}r {DM}-{V}erkaufsdaten", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/zweiter_berichtszeitraum#diplomarbeiten_master_s_theses", year = "2009", } @conference{response-time-NP-hard, author = "Friedrich Eisenbrand and Thomas Rothvo{\ss}", abstract = "In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d_i = 0: \sum_{i=1}^n (floor(Q-d_i)/p_i) + 1) * c_i ls with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is (weakly) coNP-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah {\&} Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation.", booktitle = "21st {S}ymposium on {D}iscrete {A}lgorithms ({SODA} 2010)", keywords = "periodic scheduling; complexity theory", pages = "1029--1034", title = "{EDF}-schedulability of synchronous periodic task systems is co{NP}-hard", url = "http://www.siam.org/proceedings/soda/2010/SODA10_083_eisenbrandf.pdf", year = "2010", } @conference{BergerMueller-HannemannRechnerZock11, author = "Annabell Berger and Matthias M{\"u}ller-Hannemann and Steffen Rechner and Alexander Zock", booktitle = "WALCOM 2011", pages = "77-88", publisher = "Springer, Heidelberg", series = "LNCS", title = "{E}fficient {C}omputation of {T}ime-{D}ependent {C}entralities in {A}ir {T}ransportation {N}etworks", year = "2011", } @conference{frede_et_al:DSP:2008:1584, author = "Lennart Frede and Matthias M{\"u}ller-Hannemann and Mathias Schnee", address = "Dagstuhl, Germany", booktitle = "ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems ", editor = "Matteo Fischetti and Peter Widmayer", publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany", title = "{E}fficient {O}n-{T}rip {T}imetable {I}nformation in the {P}resence of {D}elays", url = "http://drops.dagstuhl.de/opus/volltexte/2008/1584", year = "2008", } @article{N1, author = "Christoph Buchheim and Giovanni Rinaldi", journal = "SIAM Journal on Optimization", number = "4", pages = "1398-1413", title = "{E}fficient {R}eduction of {P}olynomial {Z}ero-{O}ne {O}ptimization to the {Q}uadratic {C}ase", url = "http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zaik2005-503", volume = "18", year = "2007", } @conference{Mueller-HannemannSchnee09, author = "Matthias M{\"u}ller-Hannemann and Mathias Schnee", booktitle = "Robust and Online Large-Scale Optimization", editor = "Ravindra K. Ahuja and Rolf H. M{\"o}hring and Christos D. Zaroliagis", pages = "249-272", publisher = "Springer, Heidelberg", series = "Lecture Notes in Computer Science", title = "{E}fficient {T}imetable {I}nformation in the {P}resence of {D}elays", url = "http://dx.doi.org/10.1007/978-3-642-05465-5_10", volume = "5868", year = "2009", } @mastersthesis{Salehi2011, author = "Massud Salehi", school = "Universit{\"a}t zu K{\"o}ln", title = "{E}ffiziente {H}euristiken zur {E}xtraktion von {K}uratowski-{S}ubgraphen", year = "2011", } @mastersthesis{GraphDrawing17, author = "Mathias Jansen", note = "Diplomarbeit", title = "{E}in {B}ranch-and-{C}ut {A}nsatz f{\"u}r das {M}aximum {C}-planare {S}ubgraphen {P}roblem", year = "2007", } @mastersthesis{Borchert2012, author = "Christian Borchert", school = "Universit{\"a}t zu K{\"o}ln", title = "{E}inbetten und {Z}eichnen von {B}{\"a}umen in orthogonale {F}l{\"a}chen", year = "2012", } @article{BeckmannSuscom11, author = "Andreas Beckmann and Ulrich Meyer and Peter Sanders and Johannes Singler", journal = "Sustainable Computing: Informatics and Systems", number = "2", pages = "151--163", title = "{E}nergy-efficient sorting using solid state disks", volume = "1", year = "2011", } @conference{EcoSortIGCC2010, author = "Andreas Beckmann and Ulrich Meyer and Peter Sanders and Johannes Singler", address = " ", booktitle = "1st International Green Computing Conference", crossref = " ", editor = " ", month = " ", note = "accepted for publication", number = " ", organization = " ", pages = " ", publisher = " ", series = " ", title = "{E}nergy-{E}fficient {S}orting using {S}olid {S}tate {D}isks", volume = " ", year = "2010", } @conference{dggw-ecgc-08, author = "Daniel Delling and Marco Gaertler and Robert G{\"o}rke and Dorothea Wagner", booktitle = "Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM'08)", month = "June", pages = "131--142", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{E}ngineering {C}omparators for {G}raph {C}lusterings", url = "http://dx.doi.org/10.1007/978-3-540-68880-8_14", volume = "5034", year = "2008", } @article{hswpz-epsa-09, author = "Martin Holzer and Frank Schulz and Dorothea Wagner and Grigorios Prasinos and Christos Zaroliagis", journal = "ACM Journal of Experimental Algorithmics", month = "December", number = "1", pages = "1--31", title = "{E}ngineering planar separator algorithms", url = "http://doi.acm.org/10.1145/1498698.1571635", volume = "14", year = "2009", } @phdthesis{h-epssp-08, author = "Martin Holzer", institution = "Universit{\"a}t Karlsruhe (TH)", month = "June", school = "Department of Informatics", title = "{E}ngineering {P}lanar-{S}eparator and {S}hortest-{P}ath {A}lgorithms", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000009237", year = "2008", } @conference{dggnw-ectea-07, author = "Daniel Delling and Marco Gaertler and Robert G{\"o}rke and Zoran Nikoloski and Dorothea Wagner", booktitle = "Proceedings of the European Conference of Complex Systems (ECCS'07)", month = "October", note = "Poster", title = "{E}ngineering the evaluation of clustering techniques", url = "http://cssociety.org/ECCS07-Programme", year = "2007", } @mastersthesis{Gronemann09m, author = "Martin Gronemann", school = "Lehrstuhl f{\"u}r Algorithm Engineering, Fakult{\"a}t f{\"u}r Informatik, Technische Universit{\"a}t Dortmund", title = "{E}ngineering the {F}ast-{M}ultipole-{M}ultilevel {M}ethod for multicore and {SIMD} architectures", year = "2009", } @conference{goerigk-schoebel-sea11, author = "Marc Goerigk and Anita Sch{\"o}bel", booktitle = "Proc. of the 10th International Symposium on Experimental Algorithms (SEA 11)", editor = "P. M. Pardalos and S. Rebennack", pages = "181--192", publisher = "Springer", series = "LNCS", title = "{E}ngineering the {M}odulo {N}etwork {S}implex {H}euristic for the {P}eriodic {T}imetabling {P}roblem", volume = "6630", year = "2011", } @misc{l-emg-10, author = "Oscar Fofie Lafou", institution = "Karlsruhe Institute of Technology (KIT)", month = "September", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{E}ngineering von {M}odularity-basiertem {G}raphenclustern,", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/zweiter_berichtszeitraum#studienarbeiten_student_projects", year = "2010", } @article{N4, author = "Christoph Buchheim and Angelika Wiegele and Lanbo Zheng", journal = "INFORMS Journal on Computing", number = "1", pages = "168-177", title = "{E}xact {A}lgorithms for the {Q}uadratic {L}inear {O}rdering {P}roblem", url = "http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zaik2007-560", volume = "22", year = "2010", } @conference{N6, author = "Frank Baumann and Christoph Buchheim and Frauke Liers", booktitle = "9th International Symposium on Experimental Algorithms – SEA 2010", pages = "118-128", series = "LNCS", title = "{E}xact {B}ipartite {C}rossing {M}inimization under {T}ree {C}onstraints", url = "http://dx.doi.org/10.1007/978-3-642-13193-6_11", volume = "6049", year = "2010", } @phdthesis{GraphDrawing9, author = "Markus Chimani", school = "Technische Universit{\"a}t Dortmund", title = "{E}xact {C}rossing {M}inimization", year = "2008", } @article{quantification, author = "Robert I. Davis and Thomas Rothvo{\ss} and Sanjoy K. Baruah and Alan Burns", journal = "Real-Time Systems", title = "{E}xact quantification of the suboptimality of uniprocessor fixed priority pre-emptive scheduling", url = "http://www.springerlink.com/content/171171673050622n/", volume = "43", year = "2009", } @misc{s-eedgca-09, author = "Christian Staudt", institution = "Karlsruhe Institute of Technology (KIT)", month = "February", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{E}xperimental {E}valuation of {D}ynamic {G}raph {C}lustering {A}lgorithms", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/zweiter_berichtszeitraum#studienarbeiten_student_projects", year = "2010", } @conference{KliSri09, author = "Lasse Kliemann and Anand Srivastav", booktitle = "Proceedings of the 8th International Symposium on Experimental and Efficient Algorithms (SEA)", pages = "185--196", title = "{E}xperimental {S}tudy of {N}on-{O}blivious {G}reedy and {R}andomized {R}ounding {A}lgorithms for {H}ypergraph b-{M}atching", year = "2009", } @conference{mel:GamrathLuebbecke:10, author = "Gerald Gamrath and Marco E. L{\"u}bbecke", address = "Berlin", booktitle = "Proceedings of the 9th International Symposium on Experimental Algorithms (SEA)", doi = "http://dx.doi.org/10.1007/978-3-642-13193-6_21", editor = "P. Festa", journal = "Experimental Algorithms", pages = "239--252", publisher = "Springer-Verlag", series = "Lect. Notes Comput. Sci.", title = "{E}xperiments with a {G}eneric {D}antzig-{W}olfe {D}ecomposition for {I}nteger {P}rograms", volume = "6049", year = "2010", } @conference{AlthausD09, author = "Ernst Althaus and Daniel Dumitriu", booktitle = "8th International Symposium on Experimental Algorithms (SEA)", pages = "40-50", title = "{F}ast and {A}ccurate {B}ounds on {L}inear {P}rograms", url = "http://dx.doi.org/10.1007/978-3-642-02011-7_6", year = "2009", } @conference{BergerGrimmerMuellerHannemann10, author = "Annabell Berger and Martin Grimmer and Matthias M{\"u}ller-Hannemann", booktitle = "SEA 2010", editor = "P. Festa", pages = "35-46", publisher = "Springer Heidelberg", series = "Lecture Notes in Computer Science", title = "{F}ully dynamic speed-up techniques for multi-criteria shortest paths searches in time-dependent networks", url = "http://dx.doi.org/10.1007/978-3-642-13193-6_4", volume = "6049", year = "2010", } @phdthesis{Schnee09, author = "Mathias Schnee", note = "Published in 2010 by S{\"u}dwestdeutscher Verlag f{\"u}r Hochschulschriften, ISBN-13: 978-3838117805", school = "Fachbereich Informatik, Technische Universit{\"a}t Darmstadt", title = "{F}ully realistic multi-criteria timetable information systems", year = "2009", } @techreport{dhw-dhgcum-11, author = "Christof Doll and Tanja Hartmann and Dorothea Wagner", institution = "ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT)", note = "Karlsruhe Reports in Informatics 2011-10", title = "{F}ully-{D}ynamic {H}ierarchical {G}raph {C}lustering {U}sing {C}ut {T}rees", url = "http://digbib.ubka.uni-karlsruhe.de/volltexte/1000022450", year = "2011", } @mastersthesis{GraphDrawing20, author = "Michael Bachra", note = "Diplomarbeit", title = "{G}eradliniges {Z}eichnen von {C}luster-{G}raphen im {D}ivide-and-{C}onquer-{A}nsatz", year = "2007", } @conference{5470444, author = "Nikolaj Leischner and Vitaly Osipov and Peter Sanders", abstract = "In this paper, we present the design of a sample sort algorithm for manycore GPUs. Despite being one of the most efficient comparison-based sorting algorithms for distributed memory architectures its performance on GPUs was previously unknown. For uniformly distributed keys our sample sort is at least 25% and on average 68% faster than the best comparison-based sorting algorithm, GPU Thrust merge sort, and on average more than 2 times faster than GPU quicksort. Moreover, for 64-bit integer keys it is at least 63% and on average 2 times faster than the highly optimized GPU Thrust radix sort that directly manipulates the binary representation of keys. Our implementation is robust to different distributions and entropy levels of keys and scales almost linearly with the input size. These results indicate that multi-way techniques in general and sample sort in particular achieve substantially better performance than two-way merge sort and quicksort.", address = " ", booktitle = "24th IEEE International Symposium on Parallel and Distributed Processing (IPDPS)", crossref = " ", editor = " ", organization = " ", pages = "1 -10", publisher = " ", series = " ", title = "{GPU} {S}ample {S}ort", url = "http://dx.doi.org/10.1109/IPDPS.2010.5470444", year = "2010", } @incollection{MutHandbook2009, author = "Carsten Gutwenger and Seok-Hee Hong and Petra Mutzel and Peter Eades", booktitle = "Algorithms and Theory of Computation Handbook", chapter = "6", editor = "M. Atallah and M. Blanton", note = "Second Edition", pages = "6-1--6-28", publisher = "Chapman and Hall", series = "CRC Applied Algorithms and Data Structures series", title = "{G}raph {D}rawing {A}lgorithms", volume = "2", year = "2009", } @article{Demetrescu2011, author = "Camil Demetrescu and Michael Kaufmann and Stephen G. Kobourov and Petra Mutzel", journal = "Dagstuhl Reports", number = "5", pages = "47-60", title = "{G}raph {D}rawing with {A}lgorithm {E}ngineering {M}ethods ({D}agstuhl {S}eminar 11191)", volume = "1", year = "2011", } @article{MeyerhenkeMS09graph, author = "Henning Meyerhenke and Burkhard Monien and Stefan Schamberger", journal = "Parallel Computing", number = "10--11", pages = "544--569", title = "{G}raph {P}artitioning and {D}isturbed {D}iffusion", url = "http://dx.doi.org/10.1016/j.parco.2009.09.006", volume = "35", year = "2009", } @article{AckermannBlomerScholz2011, author = "Marcel R. Ackermann and Johannes Bl{\"o}mer and Christoph Scholz", journal = "Electronic Colloquium on Computational Complexity, ECCC", note = "Report no. TR11-015.", number = "15", pages = "1--20", title = "{H}ardness and {N}on-{A}pproximability of {B}regman {C}lustering {P}roblems", url = "http://eccc.uni-trier.de/report/2011/015/", volume = "18", year = "2011", } @article{GiannopoulosKWW12, author = "Panos Giannopoulos and Christian Knauer and Magnus Wahlstr{\"o}m and Daniel Werner", journal = "J. Complexity", number = "2", pages = "162-176", title = "{H}ardness of discrepancy computation and -net verification in high dimension", volume = "28", year = "2012", } @misc{d-hccds-11, author = "Christof Doll", institution = "Karlsruhe Institute of Technology (KIT)", month = "February", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{H}ierarchical {C}ut {C}lustering in {D}ynamic {S}cenarios", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/zweiter_berichtszeitraum#studienarbeiten_student_projects", year = "2011", } @article{GunkelSchneeMueller-Hannemann11, author = "Thorsten Gunkel and Mathias Schnee and Matthias M{\"u}ller-Hannemann", journal = "Networks", number = "1", pages = "19-27", title = "{H}ow to find good night train connections", volume = "57", year = "2011", } @incollection{springerlink:10.1007/978-3-642-04107-5_20, author = "Benjamin Doerr and Michael Gnewuch and Magnus Wahlstr{\"o}m", booktitle = "Monte Carlo and Quasi-Monte Carlo Methods 2008", editor = "L' Ecuyer, Pierre and Owen, Art B.", isbn = "978-3-642-04107-5", note = "10.1007/978-3-642-04107-5_20", pages = "323-338", publisher = "Springer Berlin Heidelberg", title = "{I}mplementation of a {C}omponent-{B}y-{C}omponent {A}lgorithm to {G}enerate {S}mall {L}ow-{D}iscrepancy {S}amples", url = "http://dx.doi.org/10.1007/978-3-642-04107-5_20", year = "2009", } @techreport{GleiStefWolt12, author = "Ambros M. Gleixner and Daniel E. Steffy and Kati Wolter", abstract = "We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We demonstrate that this algorithm is effective in practice for computing extended precision solutions and that this leads to direct improvement of the best known methods for solving LPs exactly over the rational numbers.", institution = "Zuse Institute Berlin", note = "Accepted for publication in proceedings of ISSAC 2012: 37th International Symposium on Symbolic and Algebraic Computation", number = "12-19", title = "{I}mproving the {A}ccuracy of {L}inear {P}rogramming {S}olvers with {I}terative {R}efinement", type = "ZIB-Report", url = "http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1545", year = "2012", } @conference{ElOFreSriS11, author = "El Ouali, Mourad and Antje Fretwurst and Anand Srivastav", booktitle = "Proceedings of the 5th International Workshop on Algorithms and Computation, New Delhi, India, February 2011 (WALCOM 2011)", doi = "10.1007/978-3-642-19094-0_8", pages = "57-69", title = "{I}napproximability of $b$-{M}atching in $k$-uniform {H}ypergraphs", year = "2011", } @mastersthesis{GraphDrawing15, author = "Christian Wolf", note = "Diplomarbeit", title = "{I}nserting a vertex into a planar graph", year = "2008", } @conference{1496812, author = "Markus Chimani and Carsten Gutwenger and Petra Mutzel and Christian Wolf", address = "Philadelphia, PA, USA", booktitle = "SODA '09: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms", pages = "375--383", publisher = "Society for Industrial and Applied Mathematics", title = "{I}nserting a vertex into a planar graph", year = "2009", } @article{mel:HoehnKoenigLuebbeckeMoehring:11, author = "Wiebke H{\"o}hn and Felix G. K{\"o}nig and Marco E. L{\"u}bbecke and Rolf H. M{\"o}hring", doi = "10.1287/mnsc.1100.1302", journal = "Management Science", number = "4", pages = "647-666", title = "{I}ntegrated sequencing and scheduling in coil coating", volume = "57", year = "2011", } @article{HoeKoeLueMoe11, author = "Wiebke H{\"o}hn and Felix G. K{\"o}nig and Marco E. L{\"u}bbecke and Rolf H. M{\"o}hring", abstract = "We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Different coil geometries and changes of colors necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks. This can either reduce the number of setups needed or enable setups concurrent with production. A production plan comprises the sequencing of coils and the scheduling of color tanks and setup work. The aim is to minimize the makespan for a given set of coils. We present an optimization model for this integrated sequencing and scheduling problem. A core component is a graph theoretical model for concurrent setup scheduling. It is instrumental for building a fast heuristic that is embedded into a genetic algorithm to solve the sequencing problem. The quality of our solutions is evaluated via an integer program based on a combinatorial relaxation, showing that our solutions are within 10% of the optimum. Our algorithm is implemented at Salzgitter Flachstahl GmbH, a major German steel producer. This has led to an average reduction in makespan by over 13% and has greatly exceeded expectations.", institution = "Technische Universit{\"a}t Berlin", journal = "Management Science", number = "4", pages = "647-666", title = "{I}ntegrated {S}equencing and {S}cheduling in {C}oil {C}oating", url = "http://www.math.tu-berlin.de/coga/publications/techreports/2009/Report-001-2009.xhtml", volume = "57", year = "2011", } @misc{GraphDrawing5, author = "Dorothea Emig and Melissa S. Cline and Karsten Klein and Anne Kunert and Petra Mutzel and Thomas Lengauer and Mario Albrecht", booktitle = "BioMed Conference on Targeting and Tinkering with Interaction Networks", note = "poster", title = "{I}ntegration and visualization of exon expression data with domain interaction networks", } @article{DBLP:journals/jib/EmigCKKMLA08, author = "Dorothea Emig and Melissa S. Cline and Karsten Klein and Anne Kunert and Petra Mutzel and Thomas Lengauer and Mario Albrecht", journal = "J. Integrative Bioinformatics", number = "2", title = "{I}ntegrative {V}isual {A}nalysis of the {E}ffects of {A}lternative{S}plicing on {P}rotein {D}omain {I}nteraction {N}etworks", volume = "5", year = "2008", } @article{cite-key, author = "Stefan Wetzel and Karsten Klein and Steffen Renner and Daniel Rauh and Tudor I Oprea and Petra Mutzel and Herbert Waldmann", isbn = "1552-4450", journal = "Nat Chem Biol", month = "08", number = "8", pages = "581--583", publisher = "Nature Publishing Group", title = "{I}nteractive exploration of chemical space with {S}caffold {H}unter", url = "http://dx.doi.org/10.1038/nchembio.187", volume = "5", year = "2009", } @phdthesis{K11, author = "Karsten Klein", school = "TU Dortmund", title = "{I}nteractive {G}raph {D}rawing with {C}onstraints", year = "2011", } @techreport{GraphDrawing8, author = "Michael J{\"u}nger and Michael Schulz", institution = "Universit{\"a}t zu K{\"o}ln", title = "{I}ntersection graphs in simultaneous embedding with fixed edges", year = "2009", } @mastersthesis{Kuhnke2011, author = "Sascha D. Kuhnke", note = "Bachelor Thesis", school = "Universit{\"a}t zu K{\"o}ln", title = "{K}ompaktierung einer orthogonalen {Z}eichnung", year = "2011", } @mastersthesis{Stadler2011, author = "Tobias Stadler", note = "Master thesis", school = "Technische Universit{\"a}t M{\"u}nchen", title = "{K}onstruktion von komprimierten {I}ndizes f{\"u}r riesige {T}exte", url = "http://www14.in.tum.de/diplomarbeiten/abgeschlossen/2011-stadler.pdf", year = "2011", } @mastersthesis{SondernDA, author = "Sebastian Sondern", school = "Technische Universit{\"a}t Dortmund", title = "{K}onzeption und {R}ealisierung einer {G}raphenbibliothek zur {E}valuierung von {V}isualisierungsmethoden f{\"u}r {G}raphen ", year = "2011", } @article{1671975, author = "Markus Chimani and Carsten Gutwenger and Petra Mutzel and Hoi-Ming Wong", address = "New York, NY, USA", issn = "1084-6654", journal = "J. Exp. Algorithmics", pages = "2.1--2.27", publisher = "ACM", title = "{L}ayer-free upward crossing minimization", url = "http://doi.acm.org/10.1145/1671973.1671975", volume = "15", year = "2010", } @conference{DBLP:conf/wea/ChimaniGMW08, author = "Markus Chimani and Carsten Gutwenger and Petra Mutzel and Hoi-Ming Wong", booktitle = "WEA", crossref = "DBLP:conf/wea/2008", pages = "55-68", title = "{L}ayer-{F}ree {U}pward {C}rossing {M}inimization", year = "2008", } @mastersthesis{GraphDrawing19, author = "Anne Kunert", note = "Diplomarbeit", title = "{L}ayoutverfahren f{\"u}r biologische {N}etzwerke", year = "2007", } @conference{DemSinLibraries2010, author = "Roman Dementiev and Johannes Singler", address = " ", booktitle = "Algorithm Engineering", crossref = " ", editor = " ", month = " ", note = "to appear", number = " ", organization = " ", pages = " ", publisher = "Springer-Verlag", series = "LNCS", title = "{L}ibraries", volume = "5971", year = "2010", } @techreport{Scho10, author = "A. Sch{\"o}bel", institution = "Preprint-Reihe, Institut f{\"u}r Numerische und Angewandte Mathematik, Georg-August Universit{\"a}t G{\"o}ttingen", note = "submitted", title = "{L}ight {R}obustness and the trade-off between robustness and nominal quality", year = "2010", } @misc{k-lphgm-08, author = "Manuel Krings", institution = "Universit{\"a}t Karlsruhe (TH)", month = "February", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{LP}-basierte {H}euristiken f{\"u}r {G}raphenclusterung mit {M}odularity als {Q}ualit{\"a}tsma{\ss}", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#studienarbeiten_student_projects", year = "2008", } @techreport{HoltgreweMason, author = "Manuel Holtgrewe", institution = "Fachbereich f{\"u}r Mathematik und Informatik, Freie Universit{\"a}t Berlin", keywords = "benchmarks; experiments", month = "October", number = "TR-B-10-06", title = "{M}ason - a read simulator for second generation sequencing data", url = "http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000006687", year = "2010", } @conference{Kli11, author = "Lasse Kliemann", booktitle = "Proceedings of the 10th International Symposium on Experimental and Efficient Algorithms, Kolimpari, Chania, Crete, Greece, May 2011 (SEA 2011)", doi = "10.1007/978-3-642-20662-7_22", note = "Document ID: dda51148-ac5b-4655-9c4f-e01f26511235", pages = "254-266", title = "{M}atching in {B}ipartite {G}raph {S}treams in a {S}mall {N}umber of {P}asses ({E}xtended {A}bstract)", year = "2011", } @misc{f-mss-07, author = "Myriam Freidinger", institution = "Universit{\"a}t Karlsruhe (TH)", month = "February", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{M}inimale {S}chnitte und {S}chnittb{\"a}ume", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#studienarbeiten_student_projects", year = "2007", } @article{KochAchterbergAndersenetal.2011, author = "Thorsten Koch and Tobias Achterberg and Erling Andersen and Oliver Bastert and Timo Berthold and Robert E. Bixby and Emilie Danna and Gerald Gamrath and Ambros M. Gleixner and Stefan Heinz and Andrea Lodi and Hans Mittelmann and Ted Ralphs and Domenico Salvagnin and Daniel E. Steffy and Kati Wolter", institution = "Zuse Institute Berlin", journal = "Mathematical Programming Computation", number = "10-31", pages = "103-163", title = "{MIPLIB} 2010", type = "ZIB-Report", url = "http://vs24.kobv.de/opus4-zib/frontdoor/index/index/docId/1295", volume = "3", year = "2011", } @misc{Pukall10, author = "K.-M. Pukall", howpublished = "Bachelor Thesis, Goethe University Frankfurt am Main", month = "July", title = "{M}odelling and {A}nalysis of {F}lash {M}emory {T}ranslation {L}ayers", year = "2010", } @conference{gmsw-mdcdg-10a, author = "Robert G{\"o}rke and Pascal Maillard and Christian Staudt and Dorothea Wagner", booktitle = "Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10)", editor = "Paola Festa", month = "May", pages = "436--448", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{M}odularity-{D}riven {C}lustering of {D}ynamic {G}raphs", url = "http://dx.doi.org/10.1007/978-3-642-13193-6_37", volume = "6049", year = "2010", } @conference{DisserMueller-HannemannSchnee08, author = "Yann Disser and Matthias M{\"u}ller-Hannemann and Mathias Schnee", booktitle = "WEA", pages = "347-361", publisher = "Springer, Heidelberg", series = "Lecture Notes in Computer Science", title = "{M}ulti-criteria {S}hortest {P}aths in {T}ime-{D}ependent {T}rain {N}etworks", url = "http://dx.doi.org/10.1007/978-3-540-68552-4_26", volume = "5038", year = "2008", } @conference{OsiSan10b, author = "Vitaly Osipov and Peter Sanders", abstract = "We present a multi-level graph partitioning algorithm based on the extreme idea to contract only a single edge on each level of the hierarchy. This obviates the need for a matching algorithm and promises very good partitioning quality since there are very few changes between two levels. Using an efficient data structure and new flexible ways to break local search improvements early, we obtain an algorithm that scales to large inputs and produces the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 155 improvements dominating the entries for large graphs.", address = " ", booktitle = "18th European Symposium on Algorithms (ESA)", crossref = " ", editor = " ", month = " ", note = "to appear", number = " ", organization = " ", pages = " ", publisher = " ", series = "LNCS", title = "{N}-{L}evel {G}raph {P}artitioning", volume = " ", year = "2010", } @article{mel:HennigNygreenLuebbecke:11, author = "Frank Hennig and Bj{\o}rn Nygreen and Marco E. L{\"u}bbecke", doi = "10.1002/nav.21489", journal = "Naval Research Logistics", number = "3-4", pages = "298-310", title = "{N}ested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery", volume = "59", year = "2012", } @conference{DBLP:conf/tapas/MeyerNW11, author = "Ulrich Meyer and Andrei Negoescu and Volker Weichert", booktitle = "Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings", crossref = "DBLP:conf/tapas/2011", pages = "217-228", series = "Lecture Notes in Computer Science", title = "{N}ew {B}ounds for {O}ld {A}lgorithms: {O}n the {A}verage-{C}ase {B}ehavior of {C}lassic {S}ingle-{S}ource {S}hortest-{P}aths {A}pproaches", volume = "6595", year = "2011", } @conference{EisenbrandRothvossDDA09, author = "F. Eisenbrand and T. Rothvo{\ss}", abstract = "We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector alpha, an error bound epsilon and a denominator bound N. One has to decide whether there exists an integer, called the denominator Q with 1 <= Q <= N such that the distance of each number Q*alpha_i to its nearest integer is bounded by epsilon. Lagarias has shown that this problem is NP-complete and optimization versions have been shown to be hard to approximate within a factor n^c/ log log n for some constant c > 0. We strengthen the existing hardness results and show that the optimization problem of finding the smallest denominator Q such that the distances of Q*alpha_i to the nearest integer is bounded by epsilon is hard to aproximate within a factor 2^n unless P=NP. We then outline two further applications of this strengthening: We show that a directed version of Diophantine approximation is also hard to approximate. Furthermore we prove that the mixing set problem with arbitrary capacities is NP-hard. This solves an open problem raised by Conforti, Di Summa and Wolsey.", booktitle = "Proceedings of the 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009)", doi = "10.1007/978-3-642-03685-9", isbn = "978-3-642-03684-2", keywords = "Diophantine approximation; NP-hardness", pages = "98--110", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{N}ew {H}ardness {R}esults for {D}iophantine {A}pproximation", url = "http://cui.unige.ch/tcs/random-approx/2009/index.php", volume = "5687", year = "2009", } @mastersthesis{Schallaboeck2011, author = "Moritz Schallab{\"o}ck", school = "Lehrstuhl f{\"u}r Algorithm Engineering, Fakult{\"a}t f{\"u}r Informatik, Technische Universit{\"a}t Dortmund", title = "{N}ew {O}ptimal {C}ompaction {S}trategies for {O}rthogonal {G}raph {L}ayout", year = "2011", } @phdthesis{Monemizadeh2010, author = "Morteza Monemizadeh", school = "TU Dortmund", title = "{N}on-uniform {S}ampling in {C}lustering and {S}treaming", year = "2010", } @conference{AjwaniBJMM09, author = "Deepak Ajwani and Andreas Beckmann and Riko Jacob and Ulrich Meyer and Gabriel Moruz", booktitle = "8th International Symposium on Experimental Algorithms", pages = "16-27", title = "{O}n computational models for flash memory devices", url = "http://dx.doi.org/10.1007/978-3-642-02011-7_4", year = "2009", } @conference{Meyer08b, author = "Ulrich Meyer", booktitle = " 25th Annual Symposium on Theoretical Aspects of Computer Science", crossref = "DBLP:conf/stacs/2008", doi = "http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1316", publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany", series = "LIPIcs", title = "{O}n {D}ynamic {B}readth-{F}irst {S}earch in {E}xternal-{M}emory", volume = "1", year = "2008", } @article{HoeJaMe12, author = "Wiebke H{\"o}hn and Tobias Jacobs and Nicole Megow", abstract = "We consider a variant of no-wait flowshop scheduling that is motivated by continuous casting in the multistage production process in steel manufacturing. The task is to find a feasible schedule with a minimum number of interruptions, i.e., continuous idle time intervals on the last production stage. Based on an interpretation as Eulerian Extension Problems, we fully settle the complexity status of any particular problem case: We give a very intuitive optimal algorithm for scheduling on two processing stages with one machine in the first stage, and we show that all other problem variants are strongly NP-hard. We also discuss alternative idle time related scheduling models and their justification in the considered steel manufacturing environment. Here, we derive constant factor approximations.", journal = "Journal of Scheduling", pages = "295-309", title = "{O}n {E}ulerian {E}xtensions and their {A}pplication to {N}o-wait {F}lowshop {S}cheduling", url = "http://www.math.tu-berlin.de/coga/publications/techreports/2009/Report-008-2009.xhtml", volume = "15", year = "2012", } @conference{bdhggnw-fgcmm-07, author = "Ulrik Brandes and Daniel Delling and Martin H{\"o}fer and Marco Gaertler and Robert G{\"o}rke and Zoran Nikoloski and Dorothea Wagner", booktitle = "Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07)", editor = "Andreas Brandst{\"a}dt and Dieter Kratsch and Haiko M{\"u}ller", month = "October", pages = "121--132", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{O}n {F}inding {G}raph {C}lusterings with {M}aximum {M}odularity", url = "http://dx.doi.org/10.1007/978-3-540-74839-7_12", volume = "4769", year = "2007", } @article{bdgghnw-omc-08, author = "Ulrik Brandes and Daniel Delling and Marco Gaertler and Robert G{\"o}rke and Martin H{\"o}fer and Zoran Nikoloski and Dorothea Wagner", journal = "IEEE Transactions on Knowledge and Data Engineering", month = "February", number = "2", pages = "172--188", title = "{O}n {M}odularity {C}lustering", url = "http://doi.ieeecomputersociety.org/10.1109/TKDE.2007.190689", volume = "20", year = "2008", } @conference{DBLP:conf/gd/AlbrechtKKKMPSW09, author = "Andreas Kerren and Karsten Klein and Oliver Kohlbacher and Petra Mutzel and Wolfgang Paul and Falk Schreiber and Michael Wybrow and Mario Albrecht", booktitle = "Graph Drawing", crossref = "DBLP:conf/gd/2009", pages = "256--267", title = "{O}n {O}pen {P}roblems in {B}iological {N}etwork {V}isualization", year = "2009", } @techreport{Mallach2011, author = "Sven Mallach", title = "{O}n separation pairs and split components of biconnected graphs", year = "2011", } @conference{KrugerLeutnantHabumbachAckermann+2010, author = "Alexander Kr{\"u}ger and Volker Leutnant and Reinhold H{\"a}b-Umbach and Marcel R. Ackermann and Johannes Bl{\"o}mer", booktitle = "Sprachkommunikation 2010 -- Beitr{\"a}ge der 9. ITG-Fachtagung", pages = "25:1--4", publisher = "VDE Verlag", title = "{O}n the {I}nitialisation of {D}ynamic {M}odels for {S}peech {F}eatures", year = "2010", } @conference{HoeJa12b, author = "Wiebke H{\"o}hn and Tobias Jacobs", abstract = "We consider the problem of scheduling jobs on a single machine. Given some continuous cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each individual job is determined by the cost function value at the job's completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard. The main contribution of this article is a tight analysis of the approximation factor of Smith's rule under any particular convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. To overcome unrealistic worst case instances, we also give tight bounds that are parameterized by the minimum, maximum, and total processing time.", booktitle = "Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN)", pages = "482-493", publisher = "Springer", series = "LNCS", title = "{O}n the performance of {S}mith's rule in single-machine scheduling with nonlinear cost", volume = "7256", year = "2012", } @conference{Meyer08_1, author = "Ulrich Meyer", booktitle = "11th Scandinavian Workshop on Algorithm Theory", crossref = "DBLP:conf/swat/2008", doi = "http://dx.doi.org/10.1007/978-3-540-69903-3_38", isbn = "978-3-540-69900-2", pages = "426-436", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{O}n {T}rade-{O}ffs in {E}xternal-{M}emory {D}iameter {A}pproximation", volume = "5124", year = "2008", } @conference{KovacsMMN09, author = "Annamaria Kovacs and Ulrich Meyer and Gabriel Moruz and Andrei Negoescu", booktitle = "20th International Symposium on Algorithms and Computation", pages = "842-851", title = "{O}nline {P}aging for {F}lash {M}emory {D}evices", url = "http://dx.doi.org/10.1007/978-3-642-10631-6_85", year = "2009", } @unpublished{MoruzN11, author = "Gabriel Moruz and Andrei Negoescu", note = "Submitted at The 38th International Colloquium on Automata, Languages and Programming. Available online at http://www.ae.cs.uni-frankfurt.de/pdf/simple_paging.pdf", title = "{O}nline{M}in: {A} {F}ast {S}trongly {C}ompetitive {R}andomized {P}aging {A}lgorithm", year = "2011", } @mastersthesis{n-ocaic-08, author = "Stefanie Nagel", institution = "Universit{\"a}t Karlsruhe (TH)", month = "October", note = "Diplomarbeit", school = "Department of Informatics", title = "{O}ptimisation of {C}lustering {A}lgorithms for the {I}dentification of {C}ustomer {P}rofiles from {S}hopping {C}art {D}ata", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#diplomarbeiten_master_s_theses", year = "2008", } @incollection{MutEncyc2009, author = "Petra Mutzel", booktitle = "Encyclopedia of Optimization", editor = "Floudas, C.A. and Pardalos, P.M.", note = "Second Edition", pages = "2813--2820", publisher = "Springer", title = "{O}ptimization in {L}eveled {G}raphs", year = "2009", } @conference{dgsw-orca-09, author = "Daniel Delling and Robert G{\"o}rke and Christian Schulz and Dorothea Wagner", booktitle = "Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management (AAIM'09)", editor = "Andrew V. Goldberg and Yunhong Zhou", month = "June", pages = "152--165", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{ORCA} {R}eduction and {C}ontr{A}ction {G}raph {C}lustering", url = "http://dx.doi.org/10.1007/978-3-642-02158-9_14", volume = "5564", year = "2009", } @conference{packetrouting-grid, author = "Britta Peis and Martin Skutella and Andreas Wiese", abstract = "The packet routing problem, i.e., the problem to send a given set of unit-size packets through a network on time, belongs to one of the most fundamental routing problems with important practical applications, e.g., in traffic routing, parallel computing, and the design of communication protocols. The problem involves critical routing and scheduling decisions. One has to determine a suitable (short) origin-destination path for each packet and resolve occurring conflicts between packets whose paths have an edge in common. The overall aim is to find a schedule with minimum makespan. A significant topology for practical applications are grid graphs. In this paper, we therefore investigate the packet routing problem under the restriction that the underlying graph is a grid. We establish approximation algorithms and complexity results for the general problem on grids, and under various constraints on the start and destination vertices or on the paths of the packets.", booktitle = "9th Latin American Theoretical Informatics Symposium (LATIN 2010)", institution = "Technische Universit{\"a}t Berlin", keywords = "Packet Routing, Grid Graphs, Complexity, NP-hardness, Approximation Algorithms", pages = "120-130", publisher = "Springer", series = "LNCS", title = "{P}acket {R}outing on the {G}rid", url = "http://dx.doi.org/10.1007/978-3-642-12200-2_12", volume = "6034", year = "2010", } @incollection{packet-routing-WAOA, author = "Britta Peis and Martin Skutella and Andreas Wiese", abstract = "Routing of packets is one of the most fundamental tasks in a network. Limited bandwith requires that some packets cannot move to their destination directly but need to wait in intermediate nodes on their path or take detours. It is desirable to find schedules that ensure fast delivery of the packets, in particular for time critial applications. In this paper we investigate the packet routing problem theoretically. We prove that the problem cannot be approximated with a factor of $6/5-\epsilon$ for all $\epsilon>0$ unless $P=NP$. We show that restricting the graph topology to planar graphs or trees still does not allow a PTAS. For trees we give 2-approximation algorithms for the directed and the undirected case. Finally, we show that it is $NP$-hard to approximate the problem with an absolute error of $k$ for any $k\ge0$.", address = "Berlin", booktitle = "7th Workshop on Approximation and Online Algorithms (WAOA 2009)", institution = "Technische Universit{\"a}t Berlin", keywords = "Packet Routing, Complexity, NP-hardness, Approximation Algorithms", pages = "217--228", publisher = "Springer", series = "LNCS", title = "{P}acket {R}outing: {C}omplexity and {A}lgorithms", url = "http://dx.doi.org/10.1007/978-3-642-12450-1_20", volume = "5893", year = "2010", } @article{ParallelCgalCgta2010, author = "Vicente H. F. Batista and David L. Millman and Sylvain Pion and Johannes Singler", crossref = " ", journal = "Computational Geometry -- Theory and Applications", month = " ", number = "8", pages = "663-677", title = "{P}arallel {G}eometric {A}lgorithms for {M}ulti-{C}ore {C}omputers", url = "http://dx.doi.org/10.1016/j.comgeo.2010.04.008", volume = "43", year = "2010", } @conference{ParallelCgalSocg2009, author = "Vicente H. F. Batista and David L. Millman and Sylvain Pion and Johannes Singler", address = " ", booktitle = "25th Annual Symposium on Computational Geometry (SoCG)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = "217-226", publisher = " ", series = " ", title = "{P}arallel {G}eometric {A}lgorithms for {M}ulti-{C}ore {C}omputers", url = "http://doi.acm.org/10.1145/1542362.1542404", volume = " ", year = "2009", } @conference{Osipov12, author = "Vitaly Osipov", booktitle = "19th International Symposium on String Processing and Information Retrieval (SPIRE)", month = "October", publisher = "Springer", series = "LNCS", title = "{P}arallel {S}uffix {A}rray {C}onstruction for {S}hared {M}emory {A}rchitectures", year = "2012", } @conference{ParallelStlDicsHppc2007, author = "Leonor Frias and Johannes Singler", address = " ", booktitle = "Workshop on Highly Parallel Processing on a Chip (HPPC)", crossref = " ", editor = " ", month = " ", number = "4854", organization = " ", pages = "49-59", publisher = " ", series = "LNCS", title = "{P}arallelization of {B}ulk {O}perations for {STL} {D}ictionaries", url = "http://dx.doi.org/10.1007/978-3-540-78474-6_8", volume = " ", year = "2007", } @article{RueSauSlaSriWarPat10, author = "Johannes R{\"u}ckelt and Volkmar Sauerland and Thomas Slawig and Anand Srivastav and Ben A. Ward and C. Patvardhan", doi = "10.1016/j.nonrwa.2010.03.006", journal = "Nonlinear Analysis: Real World Applications", number = "5", pages = "3993-4009", title = "{P}arameter {O}ptimization and {U}ncertainty {A}nalysis in a {M}odel of {O}ceanic {CO}2 {U}ptake {U}sing a {H}ybrid {A}lgorithm and {A}lgorithmic {D}ifferentiation", volume = "11", year = "2010", } @conference{mel:BergnerCapraraFuriniLuebbeckeMalagutiTraversi:11, author = "Martin Bergner and Alberto Caprara and Fabio Furini and Marco E. L{\"u}bbecke and Enrico Malaguti and Emiliano Traversi", address = "Berlin", booktitle = "Integer Programming and Combinatorial Optimization", doi = "10.1007/978-3-642-20807-2_4", note = "To appear", number = "6655", pages = "39-51", publisher = "Springer-Verlag", series = "Lect. Notes Comput. Sci.", title = "{P}artial convexification of general {MIP}s by {D}antzig-{W}olfe reformulation", year = "2011", } @conference{shared-memory, author = "Martin Niemeier and Andreas Wiese and Sanjoy Baruah", booktitle = "Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011)", title = "{P}artitioned real-time scheduling on heterogeneous shared-memory multiprocessors", url = "http://infoscience.epfl.ch/record/164509/files/scheduling.pdf?version=1", year = "2011", } @techreport{BergerBlaarGebhardtMueller-HannemannSchnee11, author = "Annabell Berger and Christian Blaar and Andreas Gebhardt and Matthias M{\"u}ller-Hannemann and Mathias Schnee", institution = "Institut f{\"u}r Informatik, Martin-Luther-Universit{\"a}t Halle-Wittenberg", number = "2011/2", title = "{P}assenger-oriented {T}rain {D}isposition", year = "2011", } @article{DBLP:journals/jgaa/GutwengerKM08, author = "Carsten Gutwenger and Karsten Klein and Petra Mutzel", journal = "J. Graph Algorithms Appl.", number = "1", pages = "73-95", title = "{P}lanarity {T}esting and {O}ptimal {E}dge {I}nsertion with {E}mbedding {C}onstraints", volume = "12", year = "2008", } @conference{PPR-ISAAC, author = "B. Peis and S. Stiller and A. Wiese", booktitle = "Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010)", pages = "266--278", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{P}olicies for {P}eriodic {P}acket {R}outing", volume = "6507", year = "2010", } @mastersthesis{1307:Puchert:11, author = "Christian Puchert", school = "Technische Universit{\"a}t Darmstadt", title = "{P}rimal {H}euristics for {B}ranch-and-{P}rice {A}lgorithms", year = "2011", } @misc{GraphDrawing6, author = "Giuseppe Italiano and Petra Mutzel and Peter Sanders and Martin Skutella", booktitle = "Oberwolfach Report", editor = "G.F. Italiano and P. Mutzel and P. Sanders and M. Skutella", institution = "Mathematisches Forschungsinstitut Oberwolfach", title = "{P}roc. {I}ntern. {O}berwolfach {W}orkshop on {A}lgorithm {E}ngineering {O}berwolfach {R}eport {N}o. 25/2007", year = "2007", } @misc{l-p-07, author = "Steffen Lang", institution = "Universit{\"a}t Karlsruhe (TH)", month = "April", note = "Student Project, Studienarbeit", school = "Department of Informatics", title = "{P}rotein domain decomposition using spectral graph partitioning", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#studienarbeiten_student_projects", year = "2007", } @conference{KaufmannKottler2010, author = "Michael Kaufmann and Stephan Kottler", booktitle = " 17th International Symposium on Graph Drawing", keywords = "SAT, Encoding, Planarity", title = "{P}roving or {D}isproving {P}lanar {S}traight-{L}ine {E}mbeddability onto given {R}ectangles", url = "http://dx.doi.org/10.1007/978-3-642-11805-0_44", year = "2010", } @mastersthesis{GraphDrawing13, author = "Myriam Baum", note = "Diplomarbeit", title = "{Q}uasi-{O}rthogonales {Z}eichnen von {C}luster-{G}raphen mit {K}antenb{\"u}ndelungen", year = "2008", } @conference{DFS08, author = "Benjamin Doerr and Tobias Friedrich and Thomas Sauerwald", booktitle = "19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)", pages = "773--781", title = "{Q}uasirandom {R}umor {S}preading", year = "2008", } @article{DFKS11, author = "Benjamin Doerr and Tobias Friedrich and Marvin K{\"u}nnemann and Thomas Sauerwald", journal = "Journal of Experimental Algorithmics", note = "Accepted for special issue on ALENEX 2009.", title = "{Q}uasirandom {R}umor {S}preading: {A}n {E}xperimental {A}nalysis", year = "2011", } @conference{DFKS09, author = "Benjamin Doerr and Tobias Friedrich and Marvin K\"unnemann and Thomas Sauerwald", booktitle = "10th Workshop on Algorithm Engineering and Experiments (ALENEX)", pages = "145-153", title = "{Q}uasirandom {R}umor {S}preading: {A}n {E}xperimental {A}nalysis", year = "2009", } @conference{DFS09, author = "Benjamin Doerr and Tobias Friedrich and Thomas Sauerwald", booktitle = "36th International Colloquium on Automata, Languages and Programming (ICALP)", pages = "366--377", title = "{Q}uasirandom {R}umor {S}preading: {E}xpanders, {P}ush vs.\ {P}ull, and {R}obustness", year = "2009", } @conference{DBLP:conf/wea/DoerrKW10, author = "Benjamin Doerr and Marvin K\"unnemann and Magnus Wahlstr{\"o}m", booktitle = "SEA", pages = "190-201", title = "{R}andomized {R}ounding for {R}outing and {C}overing {P}roblems: {E}xperiments and {I}mprovements", year = "2010", } @conference{DW09, author = "Benjamin Doerr and Magnus Wahlstr{\"o}m", booktitle = "10th Workshop on Algorithm Engineering and Experiments (ALENEX)", pages = "162-174", title = "{R}andomized {R}ounding in the {P}resence of a {C}ardinality {C}onstraint", year = "2009", } @conference{message-routing-scheduling-APPROX, author = "Ronald Koch and Britta Peis and Martin Skutella and Andreas Wiese", abstract = "Exchanging messages between nodes of a network (e.g., embedded computers) is a fundamental issue in real-time systems involving critical routing and scheduling decisions. In order for messages to meet their deadlines, one has to determine a suitable (short) origin-destination path for each message and resolve conflicts between messages whose paths share a communication link of the network. With this paper we contribute to the theoretic foundations of real-time systems. On the one hand, we provide efficient routing strategies yielding origin-destination paths of bounded dilation and congestion. In particular, we can give good a priori guarantees on the time required to send a given set of messages which, under certain reasonable conditions, implies that all messages can be scheduled to reach their destination on time. Finally, for message routing along a directed path (which is already NP-hard), we identify a natural class of instances for which a simple scheduling heuristic yields provably optimal solutions.", booktitle = "12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009)", institution = "Technische Universit{\"a}t Berlin", keywords = "Iterative Rounding, Job Shop Scheduling, Approximation Algorithms", pages = "217--230", series = "LNCS", title = "{R}eal-{T}ime {M}essage {R}outing and {S}cheduling", url = "http://dx.doi.org/10.1007/978-3-642-03685-9_17", volume = "5687", year = "2009", } @incollection{AjwaniM10realistic, author = "Deepak Ajwani and Henning Meyerhenke", booktitle = "Algorithm Engineering. Bridging the Gap between Algorithm Theory and Practice", editor = "Matthias M{\"u}ller-Hannemann and Stefan Schirra", pages = "194--236", publisher = "Springer-Verlag", series = "Lecture Notes in Computer Science", title = "{R}ealistic {C}omputer {M}odels", volume = "5971", year = "2010", } @article{DBLP:journals/endm/Mutzel08, author = "Petra Mutzel", journal = "Electronic Notes in Discrete Mathematics", pages = "33-36", title = "{R}ecent {A}dvances in {E}xact {C}rossing {M}inimization ({E}xtended {A}bstract)", volume = "31", year = "2008", } @incollection{robustness-overview08, author = "S. Cicerone and G. D'Angelo and G. Di Stefano and D. Frigioni and A. Navarra and M. Schachtebeck and A. Sch{\"o}bel", booktitle = "Robust and Online Large-Scale Optimization", number = "5868", pages = "28-60", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{R}ecoverable robustness in shunting and timetabling", year = "2009", } @conference{GiesekeMV10, author = "Fabian Gieseke and Gabriel Moruz and Jan Vahrenhold", booktitle = "Proc. 10th IEEE International Conference on Data Mining", crossref = "DBLP:conf/icdm/2010", doi = "http://dx.doi.org/10.1109/ICDM.2010.94", pages = "815-820", title = "{R}esilient {K}-d {T}rees: {K}-{M}eans in {S}pace {R}evisited", year = "2010", } @conference{Kottler2010, author = "Stephan Kottler", booktitle = "Theory and Applications of Satisfiability Testing", keywords = "SAT, Reference Point, DMRP", title = "{SAT} {S}olving with {R}eference {P}oints", url = "http://www.springerlink.com/content/226k0805nq345287", year = "2010", } @conference{DBLP:conf/gd/KleinKMWW09, author = "Karsten Klein and Nils Kriege and Petra Mutzel and Herbert Waldmann and Stefan Wetzel", booktitle = "Graph Drawing", crossref = "DBLP:conf/gd/2009", pages = "426-427", title = "{S}caffold {H}unter - {I}nteractive {E}xploration of {C}hemical {S}pace", year = "2009", } @conference{Klein2012, author = "Karsten Klein and Nils Kriege and Petra Mutzel", booktitle = "International Conference on Information Visualization Theory and Applications (IVAPP)", note = "Best Paper Award, to appear", title = "{S}caffold {H}unter -- {V}isual {A}nalysis of {C}hemical {C}ompound {D}atabases", year = "2012", } @conference{SdmesIcde2010, author = "Mirko Rahn and Peter Sanders and Johannes Singler", address = " ", booktitle = "26th IEEE International Conference on Data Engineering (ICDE)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = "685-688", publisher = " ", series = " ", title = "{S}calable {D}istributed-{M}emory {E}xternal {S}orting", url = "http://dx.doi.org/10.1109/ICDE.2010.5447865", volume = " ", year = "2010", } @conference{GueKoeMe, author = "Elisabeth G{\"u}nther and Felix G. K{\"o}nig and Nicole Megow", abstract = "We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors. For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction. With the close relation between contiguous scheduling and strip packing, our FPTAS is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.", booktitle = "Proceedings of the 7th International Workshop on Approximation and Online Algorithms (WAOA '09)", pages = "170-181", series = "Lecture Notes in Computer Science", title = "{S}cheduling and {P}acking {M}alleable {T}asks with {P}recedence {C}onstraints of {B}ounded {W}idth", volume = "5893", year = "2010", } @conference{boeing-icalp-2010, author = "Friedrich Eisenbrand and Nicolai H{\"a}hnle and Martin Niemeier and Martin Skutella and Jos{\'e} Verschae and Andreas Wiese", booktitle = "37th International Colloquium on Automata, Languages and Programming (ICALP 2010)", pages = "299--310", title = "{S}cheduling periodic tasks in a hard real-time environment", url = "http://www.springerlink.com/content/d61x037u1ux2564g/", year = "2010", } @conference{EPFL-CONF-181146, author = "Martin Niemeier and Andreas Wiese", booktitle = "10th Workshop on Approximation and Online Algorithms (WAOA2012)", title = "{S}cheduling with an {O}rthogonal {R}esource {C}onstraint", year = "2012", } @conference{S1, author = "Ernst Althaus and Alexander Bockmayr and Matthias Elf and Michael J{\"u}nger and Thomas Kasper and Kurt Mehlhorn", booktitle = "Proceedings of the 10th Annual European Symposium on Algorithms", pages = "75-87", title = "{SCIL} - {S}ymbolic {C}onstraints in {I}nteger {L}inear {P}rogramming", url = "http://www.mpi-sb.mpg.de/SCIL/scil.ps", year = "2002", } @misc{Neumann09, author = "Christian Neumann", howpublished = "Bachelor Thesis, Goethe University Frankfurt am Main", month = "October", title = "{S}emi-{E}xternal {S}table-{M}arriage", year = "2009", } @article{GeHoeMoe11, author = "Torsten Gellert and Wiebke H{\"o}hn and Rolf H. M{\"o}hring", abstract = "We consider an integrated sequencing and scheduling problem arising at filling lines in dairy industry. Even when a processing sequence is decided, still a scheduling problem has to be solved for the sequence. This incorporates typical side constraints as they occur also in other sequencing problems in practice. Previously, we proposed a framework for general sequencing and scheduling problems: A genetic algorithm is utilized for the sequencing, incorporating a problem specifi c algorithm for the fixed-sequence scheduling. In this paper, we investigate how this approach performs for filling lines. Based on insights into structural properties of the problem, we propose di erent scheduling algorithms. In cooperation with Sachsenmilch GmbH, the algorithm was implemented for their bottleneck fi lling line, and evaluated in an extensive computational study. For the real data from production, our algorithm computes almost optimal solutions. However, as a surprising result, our simple greedy algorithms outperform the more elaborate ones in many aspects, showing interesting directions for future research.", journal = "Optimization Letters", note = "to appear", pages = "491-504", title = "{S}equencing and {S}cheduling for {F}illing {L}ines in {D}airy {P}roduction", url = "http://www.springerlink.com/content/f76364j70w216630/", volume = "5", year = "2011", } @conference{ggw-sdgc-07, author = "Marco Gaertler and Robert G{\"o}rke and Dorothea Wagner", booktitle = "Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM'07)", month = "June", pages = "11--26", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{S}ignificance-{D}riven {G}raph {C}lustering", url = "http://dx.doi.org/10.1007/978-3-540-72870-2_2", year = "2007", } @conference{FullDelaunayHierarchyAlenex2010, author = "Manuel Birn and Manuel Holtgrewe and Peter Sanders and Johannes Singler", address = " ", booktitle = "Workshop on Algorithm Engineering {{\&}} Experiments (ALENEX)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = "43-54", publisher = " ", series = " ", title = "{S}imple and {F}ast {N}earest {N}eighbor {S}earch", url = "http://www.siam.org/proceedings/alenex/2010/alx10_005_birnm.pdf", volume = " ", year = "2010", } @conference{1784937, author = "Alejandro Estrella-Balderrama and Elisabeth Gassner and Michael J{\"u}nger and Merijam Percan and Marcus Schaefer and Michael Schulz", address = "Berlin, Heidelberg", booktitle = "GD'07: Proceedings of the 15th international conference on Graph drawing", pages = "280--290", publisher = "Springer-Verlag", title = "{S}imultaneous geometric graph embeddings", year = "2008", } @phdthesis{GraphDrawing10, author = "Michael Schulz", school = "Universit{\"a}t zu K{\"o}ln", title = "{S}imultaneous {G}raph {D}rawing", year = "2008", } @conference{ListPartitioningMucocos2008, author = "Leonor Frias and Johannes Singler and Peter Sanders", address = " ", booktitle = "International Workshop on Multi-Core Computing Systems (MuCoCoS)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = " ", publisher = " ", series = " ", title = "{S}ingle-{P}ass {L}ist {P}artitioning", url = "http://dx.doi.org/10.1109/CISIS.2008.44", volume = " ", year = "2008", } @article{ListPartitioningScpe, author = "Leonor Frias and Johannes Singler and Peter Sanders", crossref = " ", journal = "Scalable Computing: Practice and Experience", month = " ", number = "3", pages = "179-184", title = "{S}ingle-{P}ass {L}ist {P}artitioning", url = "http://www.scpe.org/vols/vol09/no3/SCPE_9_3_03.pdf", volume = "9", year = "2008", } @conference{DoerrFF11, author = "Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich", booktitle = "STOC", note = "To appear.", title = "{S}ocial {N}etworks {S}pread {R}umors in {S}ublogarithmic {T}ime", year = "2011", } @misc{GraphDrawing7, author = "Stefan Wetzel and Karsten Klein and Ansgar Schuffenhauer and Peter Ertl and Petra Mutzel and Herbert Waldmann", booktitle = "4th Joint Sheeld Conference on Chemoinformatics", note = "poster", title = "{S}oftware-assisted scaffold tree analysis of large compound collections", year = "2007", } @conference{avionics-IP, author = "Friedrich Eisenbrand and Martin Niemeier and Martin Skutella and Jos{\'e} Verschae and Andreas Wiese", booktitle = "18th Annual European Symposium on Algorithms (ESA 2010)", publisher = "Springer", title = "{S}olving an {A}vionics {R}eal-{T}ime {S}cheduling {P}roblem by {A}dvanced {IP}-{M}ethods", url = "http://www.springerlink.com/content/k0263q06586075q6/", year = "2010", } @article{N5, author = "Christoph Buchheim and Frauke Liers and Marcus Oswald", journal = "Mathematical Programming (Series B)", number = "1-2", pages = "513-535", title = "{S}peeding up {IP}-based {A}lgorithms for {C}onstrained {Q}uadratic 0-1 {O}ptimization", url = "http://www.zaik.uni-koeln.de/~paper/preprints.html?show=zaik2008-578", volume = "124", year = "2010", } @conference{Static-priority-response-time, author = "Friedrich Eisenbrand and Thomas Rothvo{\ss}", booktitle = "29th IEEE Real-Time Systems Symposium (RTSS 2008)", pages = "397--406", title = "{S}tatic-priority real-time scheduling: {R}esponse time computation is {NP}-hard", url = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4700453{\&}tag=1", year = "2008", } @techreport{BergerGebhardtMueller-HannemannOstrowski11, author = "Annabell Berger and Andreas Gebhardt and Matthias M{\"u}ller-Hannemann and Martin Ostrowski", institution = "Institut f{\"u}r Informatik, Martin-Luther-Universit{\"a}t Halle-Wittenberg", number = "2011/1", title = "{S}tochastic {D}elay {P}rediction in {L}arge {T}rain {N}etworks", year = "2011", } @conference{AckermannLammersenMartensRaupach+2010, author = "Marcel R. Ackermann and Christiane Lammersen and Marcus M{\"a}rtens and Christoph Raupach and Christian Sohler and Kamil Swierkot", booktitle = "Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2010", pages = "175--187", publisher = "SIAM: Society for Industrial and Applied Mathematics", title = "{S}tream{KM}tt ++: {A} {C}lustering {A}lgorithm for {D}ata {S}treams", year = "2010", } @conference{Kriege2012, author = "Nils Kriege and Petra Mutzel", booktitle = "International Conference on Machine Learning (ICML)", note = "to appear", title = "{S}ubgraph {M}atching {K}ernels for {A}ttributed {G}raphs", year = "2012", } @conference{N7, author = "Frank Baumann and Christoph Buchheim", booktitle = "International Symposium on Combinatorial Optimization – ISCO 2010", pages = "239-246", series = "Electronic Notes in Discrete Mathematics", title = "{S}ubmodular {F}ormulations for {R}ange {A}ssignment {P}roblems", url = "http://dx.doi.org/10.1016/j.endm.2010.05.031", volume = "36", year = "2010", } @techreport{BergerMueller-Hannemann09, author = "Annabell Berger and Matthias M{\"u}ller-Hannemann", institution = "Institute of Computer Science, Martin-Luther-Universit{\"a}t Halle-Wittenberg", title = "{S}ubpath-{O}ptimality of {M}ulti-{C}riteria {S}hortest {P}aths in {T}ime- and {E}vent-{D}ependent {N}etworks", url = "http://wcms.uzi.uni-halle.de/download.php?down=10850{\&}elem=2163494", year = "2009", } @article{N3, author = "Christoph Buchheim and Giovanni Rinaldi", journal = "Journal on Satisfiability, Boolean Modeling and Computation", pages = "121-139", title = "{T}erse {I}nteger {L}inear {P}rograms for {B}oolean {O}ptimization", url = "http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zaik2007-558", volume = "6", year = "2009", } @conference{GueKoeMe09, author = "Elisabeth G{\"u}nther and Felix G. K{\"o}nig and Nicole Megow", booktitle = "Proceedings of MAPSP '09", title = "{T}he {B}in-{S}cheduling {P}roblem", year = "2009", } @conference{MutCross2009, author = "Petra Mutzel", booktitle = "Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday", editor = "S. Albers and H. Alt and S. N{\"a}her", pages = "305-317", publisher = "Springer", series = "LNCS", title = "{T}he {C}rossing {N}umber of {G}raphs: {T}heory and {C}omputation", volume = "5760", year = "2009", } @mastersthesis{h-tdgcp-08, author = "Florian H{\"u}bner", institution = "Universit{\"a}t Karlsruhe (TH)", month = "May", note = "Diplomarbeit", school = "Department of Informatics", title = "{T}he {D}ynamic {G}raph {C}lustering {P}roblem - {ILP}-{B}ased {A}pproaches {B}alancing {O}ptimality and the {M}ental {M}ap", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#diplomarbeiten_master_s_theses", year = "2008", } @conference{OSS09, author = "Vitaly Osipov and Peter Sanders and Johannes Singler", abstract = "We present Filter-Kruskal - a simple modification of Kruskal's algorithm that avoids sorting edges that are "obviously" not in the MST. For arbitrary graphs with random edge weights Filter-Kruskal runs in time $\Oh{m + n\log n\log\frac{m}{n}}$, i.e. in linear time for not too sparse graphs. Experiments indicate that the algorithm has very good practical performance over the entire range of edge densities. An equally simple parallelization seems to be the currently best practical algorithm on multicore machines.", address = " ", booktitle = "10th Workshop on Algorithm Engineering and Experiments (ALENEX)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = "52--61", publisher = " ", series = " ", title = "{T}he {F}ilter-{K}ruskal {M}inimum {S}panning {T}ree {A}lgorithm", url = "http://www.siam.org/proceedings/alenex/2009/alx09_005_osipovv.pdf", volume = " ", year = "2009", } @conference{SinglerKosnikIwmse2008, author = "Johannes Singler and Benjamin Kosnik", address = " ", booktitle = "International Workshop on Multicore Software Engineering (IWMSE)", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = " ", publisher = " ", series = " ", title = "{T}he libstdc++ parallel mode: {S}oftware {E}ngineering {C}onsiderations", url = "http://doi.acm.org/10.1145/1370082.1370089", volume = " ", year = "2008", } @conference{MCSTLEuropar2007, author = "Johannes Singler and Peter Sanders and Felix Putze", address = " ", booktitle = "Euro-Par 2007: Parallel Processing", crossref = " ", editor = " ", month = " ", number = " ", organization = " ", pages = "682-694", publisher = "Springer-Verlag", series = "LNCS", title = "{T}he {M}ulti-{C}ore {S}tandard {T}emplate {L}ibrary", url = "http://dx.doi.org/10.1007/978-3-540-74466-5_72", volume = "4641", year = "2007", } @conference{Bachmaier2012, author = "Christian Bachmaier and Franz Brandenburg and Philip Effinger and Carsten Gutwenger and Jyrki Katajainen and Karsten Klein and Miro Sp{\"o}nemann and Matthias Stegmaier and Michael Wybrow", booktitle = "Graph Drawing", editor = "Marc van Kreveld, Bettina Speckmann", isbn = "978-3-642-25877-0", pages = "435-440", publisher = "Springer Berlin / Heidelberg", title = "{T}he {O}pen {G}raph {A}rchive: {A} {C}ommunity-{D}riven {E}ffort", url = "http://dx.doi.org/10.1007/978-3-642-25878-7_42", year = "2012", } @inbook{MarkusChimani2012, author = "Markus Chimani and Carsten Gutwenger and Michael J{\"u}nger and Gunnar W. Klau and Karsten Klein and Petra Mutzel", booktitle = "Handbook of Graph Drawing and Visualization", editor = "R. Tamassia", note = "to appear", publisher = "CRC Press", title = "{T}he {O}pen {G}raph {D}rawing {F}ramework ({OGDF})", year = "2012", } @techreport{GoerigkKnothMueller-HannemannSchoebelSchmidt11, author = "Marc Goerigk and Martin Knoth and Matthias M{\"u}ller-Hannemann and Anita Sch{\"o}bel and Marie Schmidt", institution = "Institut f{\"u}r Informatik, Martin-Luther-Universit{\"a}t Halle-Wittenberg", number = "2011/3", title = "{T}he {P}rice of {R}obustness in {T}imetable {I}nformation", year = "2011", } @conference{max-task, author = "Britta Peis and Andreas Wiese", booktitle = "8th Workshop on Approximation and Online Algorithms (WAOA 2010)", publisher = "Springer", series = "LNCS", title = "{T}hroughput {M}aximization for {P}eriodic {P}acket {R}outing on {T}rees and {G}rids", url = "http://www.springerlink.com/content/96l2q2898433063n/", year = "2011", } @techreport{Gronemann2011, author = "Martin Gronemann and Michael J{\"u}nger and Sven Mallach and Daniel R. Schmidt", title = "{T}owards shortest longest edges in orthogonal graph drawing", year = "2011", } @conference{DauKrugel2011, author = "Andre Dau and Johannes Krugel", abstract = "Algorithms working on sequences are influenced by the statistical properties of the sequences. Algorithms for fragment assembly for example usually produce a worse result if there are many repetitions. Also the space usage and running time of many data structures and algorithms depend on the statistical properties of the underlying text. We implemented tt-analyze, a tool to analyze sequences for certain statistical properties, among others the entropy, the number and distribution of different substrings, and the repeat structure. Besides, we also designed and implemented tt-generate, a tool to generate synthetic sequences with certain predefined properties, using models such as a Markov process, a discrete autoregressive process, and a repeat model. In bioinformatics these models have primarily been used to analyze given sequences, whereas here, we use them to also generate synthetic ones. The respective parameters of the models can be defined manually or be learned from given training data. The combination of both tools allows to generate sequences that are similar to real world sequences with respect to certain properties. This will allow to investigate the performance of algorithms under to some extent realistic, yet controlled conditions, and to determine the degree of dependence from parameters of the underlying sequence. Both tools have an extensible design which allows the integration of new modules for other statistical properties or generating models with the same programming interface.", booktitle = "German Conference on Bioinformatics 2011, Weihenstephan, Germany (GCB 2011)", month = "September", title = "{T}t-analyze and tt-generate: {T}ools to {A}nalyze and {G}enerate {S}equences with {T}rained {S}tatistical {P}roperties", year = "2011", } @conference{MeMoeSch07, author = "Nicole Megow and Rolf H. M{\"o}hring and Jens Schulz", booktitle = "Proceedings of MAPSP '07", title = "{T}urnaround {S}cheduling in {C}hemical {M}anufacturing", year = "2007", } @conference{BergerMueller-Hannemann10, author = "Annabell Berger and Matthias M{\"u}ller-Hannemann", booktitle = "Proceedings of WG 2010", pages = "220--231", publisher = "Springer, Heidelberg", series = "LNCS", title = "{U}niform {S}ampling of {D}irected {G}raphs with a {F}ixed {D}egree {S}equence", volume = "6410", year = "2010", } @conference{IPCO-general-packet-routing, author = "Britta Peis and Andreas Wiese", booktitle = "Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011)", institution = "Technische Universit{\"a}t Berlin", publisher = "Springer", title = "{U}niversal packet routing with arbitrary bandwidths and transit times", url = "ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-024-2010.pdf", year = "2011", } @phdthesis{Wong2011, author = "Hoi-Ming Wong", school = "TU Dortmund", title = "{U}pward {P}lanarization and {L}ayout", year = "2011", } @article{Chimani2011, author = "Markus Chimani and Carsten Gutwenger and Petra Mutzel and Hoi-Ming Wong", journal = "Journal of Graph Algorithms and Applications", number = "1", pages = "127--155", title = "{U}pward {P}lanarization {L}ayout", volume = "15", year = "2011", } @conference{DBLP:conf/gd/ChimaniGMW09, author = "Markus Chimani and Carsten Gutwenger and Petra Mutzel and Hoi-Ming Wong", booktitle = "Graph Drawing", crossref = "DBLP:conf/gd/2009", pages = "94-106", title = "{U}pward {P}lanarization {L}ayout", year = "2009", } @techreport{StefWolt11TR, author = "Daniel E. Steffy and Kati Wolter", institution = "Zuse Institute Berlin", note = "Accepted for publication in INFORMS Journal on Computing. ", number = "11-08", title = "{V}alid {L}inear {P}rogramming {B}ounds for {E}xact {M}ixed-{I}nteger {P}rogramming", type = "ZIB-Report", url = "http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1233", year = "2011", } @article{Chimani2012b, author = "Markus Chimani and Petr Hliněn{\'y} and Petra Mutzel", journal = "European Journal of Combinatorics", number = "3", pages = "326-335", title = "{V}ertex insertion approximates the crossing number of apex graphs", volume = "33", year = "2012", } @conference{1439744, author = "Dorothea Emig and Karsten Klein and Anne Kunert and Petra Mutzel and Mario Albrecht", address = "Washington, DC, USA", booktitle = "MEDIVIS '08: Proceedings of the 2008 Fifth International Conference BioMedical? Visualization: Information Visualization in Medical and Biomedical Informatics", pages = "36--43", publisher = "IEEE Computer Society", title = "{V}isualizing {D}omain {I}nteraction {N}etworks and the {I}mpact of {A}lternative {S}plicing {E}vents", url = "http://dx.doi.org/10.1109/MediVis.2008.16", year = "2008", } @mastersthesis{Dueppmann2012, author = "Bernd D{\"u}ppmann", school = "Universit{\"a}t zu K{\"o}ln", title = "{V}orverarbeitung von {G}raphen zur {S}eparierung von {K}uratowski-{U}ngleichungen", year = "2012", } @article{DoerrFF12a, author = "Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich", journal = "Commun. ACM", number = "6", pages = "70-75", title = "{W}hy rumors spread so quickly in social networks", volume = "55", year = "2012", } @mastersthesis{g-zgme-08, author = "Dieter Glaser", institution = "Universit{\"a}t Karlsruhe (TH)", month = "February", note = "Diplomarbeit", school = "Department of Informatics", title = "{Z}eitexpandiertes {G}raphenclustern - {M}odellierung und {E}xperimente", url = "http://i11www.iti.uni-karlsruhe.de/projects/spp1307/erster_berichtszeitraum#diplomarbeiten_master_s_theses", year = "2008", } @mastersthesis{GraphDrawing12, author = "Gereon Bartel", note = "Diplomarbeit", title = "{Z}erlegungsstrategien f{\"u}r {M}ultilevel-{G}raphdrawing-{V}erfahren", year = "2008", }