Search

This book constitutes the thoroughly refereed post-conference proceedings of the 6th International Conference on Finite Difference Methods, FDM 2014, held in Lozenetz, Bulgaria, in June 2014.The 36 revised full papers were carefully reviewed and selected from 62 submissions. These papers together with 12 invited papers cover topics such as finite difference and combined finite difference methods as well as finite element methods and their various applications in physics, chemistry, biology and finance.

This book constitutes the thoroughly refereed proceedings of the 15th International Workshop on Fast Software Encryption, FSE 2008, held in Lausanne, Switzerland in February 2008. The 26 revised full papers presented together with 4 short papers were carefully reviewed and selected from 72 submissions. The papers address all current aspects of fast and secure primitives for symmetric cryptology and are organized in topical sections on SHA collisions, new hash function designs, block cipher cryptanalysis, implementation aspects, hash function cryptanalysis, stream cipher cryptanalysis, security bounds, and entropy.

A large amount of the capacity of today's computers is used for computations that can be described as computations involving real numbers. In this book, the focus is on a problem arising particularly in real number computations: the problem of veri?edor reliablecomputations. Since real numbersare objects c- taining an in?nite amount of information, they cannot be represented precisely on a computer. This leads to the well-known problems caused by unveri?ed - plementations of real number algorithms using?nite precision. While this is t- ditionally seen to be a problem in numerical mathematics, there are also several scienti?c communities in computer science that are dealing with this problem. This book is a follow-up of the Dagstuhl Seminar 06021 on “Reliable Imp- mentation of Real Number Algorithms: Theory and Practice,” which took place January 8–13, 2006. It was intended to stimulate an exchange of ideas between the di?erent communities that deal with the problem of reliable implementation of real number algorithms either from a theoretical or from a practical point of view. Forty-eight researchers from many di?erent countries and many di?erent disciplines gathered in the castle of Dagstuhl to exchange views and ideas, in a relaxed atmosphere. The program consisted of 35 talks of 30 minutes each, and of three evening sessions with additional presentations and discussions. There were also lively discussions about di?erent theoretical models and practical - proaches for reliable real number computations.

This book constitutes the refereed proceedings of the 17th International Conference on Graph Transformation, ICGT 2024, held in Enschede, The Netherlands, during July 10–11, 2024. The 10 full papers and 3 short papers included in this book were carefully reviewed and selected from 21 submissions. They were organized in topical sections as follows: Theoretical Advances; Application Domains; and Tool and Blue Skies Presentations.

This book constitutes the refereed proceedings of the 15th International Conference on Graph Transformation, ICGT 2022, which took place Nantes, France in July 2022.The 10 full papers and 1 tool paper presented in this book were carefully reviewed and selected from 19 submissions. The conference focuses on describing new unpublished contributions in the theory and applications of graph transformation as well as tool presentation papers that demonstrate main new features and functionalities of graph-based tools.

This book constitutes the refereed proceedings of the 14th International Conference on Graph Transformation, ICGT 2021, which took place virtually during June 24-25, 2021.The 14 full papers and 2 tool papers presented in this book were carefully reviewed and selected from 26 submissions. They deal with the following topics: theoretical advances; application domains; and tool presentations.

This book constitutes the refereed proceedings of the 13th International Conference on Graph Transformation, ICGT 2020, in Bergen, Norway, in June 2020.•The 16 research papers and 4 tool paper presented in this book were carefully reviewed and selected from 40 submissions. One invited paper is also included. The papers deal with the following topics: theoretical advances; application domains; and tool presentations.•The conference was held virtually due to the COVID-19 pandemic.

This book constitutes the refereed proceedings of the 12th International Conference on Graph Transformation, ICGT 2019, held as part of STAF 2019, in Eindhoven, The Netherlands, in July2019. The 12 research papers and 1 tool paper presented in this book were carefully reviewed and selected from 22 submissions. The papers deal with the following topics: Theory, Analysis and Verification, Tools and Applications, and Transformation Rules Construction and Matching.

This book constitutes the refereed proceedings of the 11th International Conference on Graph Transformation, ICGT 2018, held as part of STAF 2018, in Toulouse, France, in June 2018.The 9 full papers, 2 short papers and 1 keynote presented in this book were carefully reviewed and selected from 16 submissions. The papers deal with the following topics: graph languages; graph transformation formalisms; parallel independence and conflicts; and graph conditions and verification.​

This book constitutes the refereed proceedings of the 10th International Conference on Graph Transformation, ICGT 2017, held as part of STAF 2017, in Marburg, Germany, in July 2017.The 14 papers presented were carefully reviewed and selected from 23 submissions. The papers cover a wide range of topics including theoretical approaches to graph transformation and their verification, model-driven engineering, chemical reactions as well as various applications. They are organized in the following topical sections: foundations; graph language and parsing; analysis and verification; and model transformation and tools.

This book constitutes the refereed proceedings of the 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016, held in Grenoble, France, in August 2016. The 47 revised full papers presented together with 2 invited papers and one industrial paper were carefully reviewed and selected from 176 submissions. The papers are organized in 12 topical sections: Support Tools and Environments; Performance and Power Modeling, Prediction and Evaluation; Scheduling and Load Balancing; High Performance Architectures and Compilers; Parallel and Distributed Data Management and Analytics; Cluster and Cloud Computing; Distributed Systems and Algorithms; Parallel and Distributed Programming, Interfaces, Languages; Multicore and Manycore Parallelism; Theory and Algorithms for Parallel Computation and Networking; Parallel Numerical Methods and Applications; Accelerator Computing.

This volume contains the papers presented at 6th Conference on Geometric Modeling and Processing (GMP 2010) held in Castro Urdiales, Spain during June16–18,2010. GeometricModelingandProcessingisabiannualinternational conference series on geometric modeling, simulation and computing. Previously, GMPhasbeenheldinHongKong(2000),Saitama,Japan(2002),Beijing,China (2004), Pittsburgh, USA (2006) and Hangzhou, China (2008). GMP 2010 received a total of 30 submissions that were reviewed by three to four Program Committee members on average. While the number of subm- sions dropped signi?cantly from previous years, the quality did not and was still quite high overall. Based on the reviews received, the committee decided to - cept 20 papers for inclusion in the proceedings. Additionally, extended versions of selected papers were considered for a special issue of Computer-Aided - sign (CAD) and Computer-Aided Geometric Design (CAGD). The paper topics spanned a wide variety and include: – Solutions of transcendental equations – Volume parameterization – Smooth curves and surfaces – Isogeometric analysis – Implicit surfaces – Computational geometry Many people helped make this conference happen and we are grateful for their help. We would especially like to thank the Conference Chair, all of the authors who submitted papers, the ProgramCommittee members who reviewed the papers and all of the participants at the conference.

While the areas of information management and management science are full of algorithmic challenges, the proliferation of data has called for the design of e?cient and e?ective algorithms and data structures for their management and processing. The International Conference on Algorithmic Aspects in Information and Management(AAIM) is intended for originalalgorithmicresearchon immediate applications and/or fundamental problems pertinent to information mana- ment and management science to be broadly construed. The conference aims at bringing together researchers in computer science, operations research, applied mathematics, economics, and related disciplines. This volume contains papers presented at AAIM 2010: the 6th International Conference on Algorithmic Aspects in Information and Management, which was held during July 19-21, 2010, in Weihai, China. We received a total of 50 s- missions.Eachsubmissionwasreviewedbythreemembersof the ProgramC- mittee or their deputies on the quality, originality, soundness, and signi?cance of its contribution. The committee decided to accept 31 papers. The program also included two invited keynote talks. The success of the conference resulted from the input of many people. We would like?rst of all to thank all the members of the Program Committee for their expert evaluation of the submissions. The local organizers in the School of Computer Science and Technology, Shandong University, did an extraordinary job, for which we are very grateful. We thank the National Natural Science Foundation of China, Montana State University (USA), University of Warwick (UK), and Shandong University (China) for their sponsorship.

This book constitutes the refereed proceedings of the 11th Algorithms and Data Structures Symposium, WADS 2009, held in Banff, Canada, in August 2009. The Algorithms and Data Structures Symposium - WADS (formerly'Workshop on Algorithms and Data Structures') is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 49 revised full papers presented in this volume were carefully reviewed and selected from 126 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

Nowadays constraint satisfaction problems (CSPs) are ubiquitous in many different areas of computer science, from artificial intelligence and database systems to circuit design, network optimization, and theory of programming languages. Consequently, it is important to analyze and pinpoint the computational complexity of certain algorithmic tasks related to constraint satisfaction. The complexity-theoretic results of these tasks may have a direct impact on, for instance, the design and processing of database query languages, or strategies in data-mining, or the design and implementation of planners. This state-of-the-art survey contains the papers that were invited by the organizers after conclusion of an International Dagstuhl-Seminar on Complexity of Constraints, held in Dagstuhl Castle, Germany, in October 2006. A number of speakers were solicited to write surveys presenting the state of the art in their area of expertise. These contributions were peer-reviewed by experts in the field and revised before they were collated to the 9 papers of this volume. In addition, the volume contains a reprint of a survey by Kolaitis and Vardi on the logical approach to constraint satisfaction that first appeared in'Finite Model Theory and its Applications', published by Springer in 2007.

The Workshop on Experimental Algorithms, WEA, is intended to be an int- national forum for research on the experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications. The emphasis of the workshop is the use of experimental me- ods to guide the design, analysis, implementation, and evaluation of algorithms, heuristics, and optimization programs. WEA 2008 was held at the Provincetown Inn, Provincetown, MA, USA, on May 30 – June 1, 2008. This was the seventh workshop of the series, after Rome (2007),Menorca(2006),Santorini(2005),RiodeJaniero(2004),Asconia(2003), and Riga (2001). This volume contains all contributed papers accepted for presentation at the workshop. The 26 contributed papers were selected by the Program Committee onthebasisofatleastthreerefereereports,somecontributedbytrustedexternal referees. In addition to the 26 contributed papers, the program contained two invited talks. Camil Demetrescu, of the University of Rome “La Sapienza,” spoke on “Visualization in Algorithm Engineering.” David S. Johnson of AT & T Labs – Research, gave a talk on “Bin Packing: From Theory to Experiment and Back Again.” We would like to thank the authors who responded to the call for papers, our invited speakers, the members of the ProgramCommittee, the external referees, and the Organizing Committee members for making this workshop possible.

The Annual International Frontiers in Algorithmics Workshop is a focused - rum on current trends in research on algorithms, discrete structures, and their applications. It intends to bring together international experts at the research frontiers in those areas to exchange ideas and to present signi?cant new results. The mission of the workshop is to stimulate the various?elds for which al- rithmics can become a crucial enabler, and to strengthen the ties between the Eastern and Western algorithmics research communities. The Second Inter- tional Frontiers in Algorithmics Workshop (FAW 2008) took place in Changsha, China, June 19–21, 2008. In response to the Call for Papers, 80 papers were submitted from 15 co- tries and regions: Canada, China, France, Germany, Greece, Hong Kong, India, Iran, Japan, Mexico, Norway, Singapore, South Korea, Taiwan, and the USA. After a six-week period of careful reviewing and discussion, the Program C- mittee accepted 32 submissions for presentation at the conference. These papers were selected for nine special focus tracks in the areas of biomedical inform- ics, discrete structures, geometric information processing and communication, games and incentive analysis, graph algorithms, internet algorithms and pro- cols, parameterized algorithms, design and analysis of heuristics, approximate and online algorithms, and machine learning. The program of FAW 2008 also included three keynote talks by Xiaotie Deng, John E. Hopcroft, and Milan Sonka.

This book constitutes the refereed proceedings of the 16th International Conference on Conceptual Structures, ICCS 2008, held in Toulouse, France, in July 2008. The 19 revised full papers presented together with 2 invited papers were carefully reviewed and selected from over 70 submissions. The scope of the contributions ranges from theoretical and methodological topics to implementation issues and applications. The papers present a family of Conceptual Structure approaches that build on techniques derived from artificial intelligence, knowledge representation, applied mathematics and lattice theory, computational linguistics, conceptual modeling, intelligent systems and knowledge management.

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.

The refereed proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science, DMTCS 2003, held in Dijon, France, in July 2003. The 18 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 35 submissions. A broad variety of topics in discrete mathematics and the theory of computing is addressed including information theory, coding, algorithms, complexity, automata, computational mathematics, combinatorial computations, graph computations, algorithmic geometry, relational methods, game-theoretic methods, combinatorial optimization, and finite state systems.

This volume contains revised versions of the papers submitted to the workshop by the participants and accepted by the program committee after a thorough reviewing process. The collection of papers included in the proceedings covers not only various expanding applications of computer algebra to scienti?c computing but also the computer algebra systems themselves and the CA algorithms. The eight earlier CASC conferences, CASC 1998, CASC 1999, CASC 2000, CASC 2001, CASC 2002, CASC 2003, CASC 2004, and CASC 2005 were held, - spectively, in St. Petersburg, Russia, in Munich, Germany, in Samarkand, Uzb- istan, in Konstanz, Germany, in Crimea, Ukraine, in Passau, Germany, in St. Petersburg, Russia, and in Kalamata, Greece, and they proved to be successful. It was E. A. Grebenikow (Computing Center of the Russian Academy of S- ences, Moscow) who drew our attention to the group of mathematicians and c- puter scientists at the Academy of Sciences of Moldova conducting research in the?eld of computer algebra. We were impressed that this group not only is concerned with applications of CA methods to problems of scienti?c computing but also c- ries out research on the fundamental principles underlying the current computer algebra systems themselves, see also their papers in the present proceedings v- ume. It was therefore decided to organize the 9th workshop on Computer Algebra in Scienti?c Computing, CASC 2006, in Chi¸ sin? au, the capital of Moldova.

The 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000) was held at Waldhaus Jakob, in Konstanz, Germany, on 15{ 17 June 2000. It was organized by the Algorithms and Data Structures Group of the Department of Computer and Information Science, University of K- stanz, and sponsored by Deutsche Forschungsgemeinschaft (DFG) and Univ- sit¨atsgesellschaft Konstanz. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions for future research. The workshop looks back on a remarkable tradition of more than a quarter of a century. Previous Workshops have been organized in various places in Europe, and submissions come from all over the world. This year, 57 attendees from 13 di erent countries gathered in the relaxing atmosphere of Lake Constance, also known as the Bodensee. Out of 51 submis- ons, the program committee carefully selected 26 papers for presentation at the workshop. This selection re?ects current research directions, among them graph and network algorithms and their complexity, algorithms for special graph cl- ses, communication networks, and distributed algorithms. The present volume contains these papers together with the survey presented in an invited lecture by Ingo Wegener (University of Dortmund) and an extended abstract of the invited lecture given by Emo Welzl (ETH Zuric ¨ h).

This book constitutes the refereed proceedings of the 9th Annual European Symposium on Algorithms, ESA 2001, held in Aarhus, Denmark, in August 2001.The 41 revised full papers presented together with three invited contributions were carefully reviewed and selected from 102 submissions. The papers are organized in topical sections on caching and prefetching, online algorithms, data structures, optimization and approximation, sequences, scheduling, shortest paths, geometry, distributed algorithms, graph algorithms, pricing, broadcasting and multicasting, graph labeling and graph drawing, and graphs.

The abstracts and papers in this volume were presented at the Fifth Annual International Computing and Combinatorics Conference (COCOON'99), which was held in Tokyo, Japan from July 26 to 28, 1999. The topics cover most aspects of theoretical computer science and combinatorics pertaining to computing. In response to the call for papers, 88 high-quality extended abstracts were submitted internationally, of which 46 were selected for presentation by the p- gram committee. Every submitted paper was reviewed by at least three program committee members. Many of these papers represent reports on continuing - search, and it is expected that most of them will appear in a more polished and complete form in scienti c journals. In addition to the regular papers, this v- ume contains abstracts of two invited plenary talks by Prabhakar Raghavan and Seinosuke Toda. The conference also included a special talk by Kurt Mehlhorn on LEDA (Library of E cient Data types and Algorithms). The Hao Wang Award (inaugurated at COCOON'97) is given to honor the paper judged by the program committee to have the greatest scienti c merit. The recipients of the Hao Wang Award 1999 were Hiroshi Nagamochi and Tos- hide Ibaraki for their paper \An Approximation for Finding a Smallest 2-Edge- Connected Subgraph Containing a Speci ed Spanning Tree'.

The 7th Annual European Symposium on Algorithms (ESA'99) is held in Prague, Czech Republic, July 16-18, 1999. This continued the tradition of the meetings which were held in – 1993 Bad Honnef (Germany) – 1994 Utrecht (Netherlands) – 1995 Corfu (Greece) – 1996 Barcelona (Spain) – 1997 Graz (Austria) – 1998 Venice (Italy) (The proceedingsof previousESA meetings were publishedas Springer LNCS v- umes 726, 855, 979, 1136, 1284, 1461.) In the short time of its history ESA (like its sister meeting SODA) has become a popular and respected meeting. The call for papers stated that the “Symposium covers research in the use, design, and analysis of ef?cient algorithms and data structures as it is carried out in c- puter science, discrete applied mathematics and mathematical programming. Papers are solicited describing original results in all areas of algorithmic research, including but not limited to: Approximation Algorithms; Combinatorial Optimization; Compu- tional Biology; Computational Geometry; Databases and Information Retrieval; Graph and Network Algorithms; Machine Learning; Number Theory and Computer Algebra; On-line Algorithms; Pattern Matching and Data Compression; Symbolic Computation.

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS'99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT'88 and WADS'89. In response to the program committee's call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS'99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

The refereed proceedings of the 8th International Workshop on Algorithms and Data Structures, WADS 2003, held in Ottawa, Ontario, Canada, in July/August 2003. The 40 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 126 submissions. A broad variety of current aspects in algorithmics and data structures is addressed.

This book constitutes the thoroughly refereed post-workshop proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, held in Boltenhagen, Germany, in June 2001.The 27 revised full papers presented together with two invited contributions were carefully reviewed and selected from numerous submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms and graph-theoretical applications in various fields.

This book constitutes the refereed proceedings of the 17th International Conference on Conceptual Structures, ICCS 2009, which took place in Moscow, Russia, on July 26-31, 2009. The 18 papers presented together with 5 invited contributions were carefully reviewed and selected from approximately 50 submissions. Originally centered around research on knowledge representation and reasoning with conceptual graphs, over the years ICCS has broadened its scope to include innovations from a wider range of theories and related practices, among them other forms of graph-based formalisms like RDF or existential graphs, formal concept analysis, semantic Web technologies, ontologies, concept mapping and more.

Networks play a central role in today's society, since many sectors employing information technology, such as communication, mobility, and transport - even social interactions and political activities - are based on and rely on networks. In these times of globalization and the current global financial crisis with its complex and nearly incomprehensible entanglements of various structures and its huge effect on seemingly unrelated institutions and organizations, the need to understand large networks, their complex structures, and the processes governing them is becoming more and more important. This state-of-the-art survey reports on the progress made in selected areas of this important and growing field, thus helping to analyze existing large and complex networks and to design new and more efficient algorithms for solving various problems on these networks since many of them have become so large and complex that classical algorithms are not sufficient anymore. This volume emerged from a research program funded by the German Research Foundation (DFG) consisting of projects focusing on the design of new discrete algorithms for large and complex networks. The 18 papers included in the volume present the results of projects realized within the program and survey related work. They have been grouped into four parts: network algorithms, traffic networks, communication networks, and network analysis and simulation.

This book constitutes the refereed proceedings of the 8th International Workshop on Algorithms in Bioinformatics, WABI 2008, held in Karlsruhe, Germany, in September 2008 as part of the ALGO 2008 meeting. The 32 revised full papers presented together with the abstract of a keynote talk were carefully reviewed and selected from 81 submissions. All current issues of algorithms in bioinformatics are addressed, reaching from mathematical tools to experimental studies of approximation algorithms and reports on significant computational analyses. The topics range in biological applicability from genome mapping, to sequence assembly, to microarray quality, to phylogenetic inference, to molecular modeling.

This volume contains the papers presented at the 11th International Wo- shop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008) and the 12th International Workshop on Randomization and Computation (RANDOM 2008), which took place concurrently at the MIT (M- sachusetts Institute of Technology) in Boston, USA, during August 25–27, 2008. APPROX focuses on algorithmic and complexity issues surrounding the development of e?cient approximate solutions to computationally di?cult problems, and was the 11th in the series after Aalborg (1998), Berkeley (1999), Saarbru ¨cken (2000), Berkeley (2001), Rome (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). RANDOM is concerned with applications of randomness to computational and combinatorial problems, and was the 12th workshop in the series following Bologna (1997), Barcelona (1998), Berkeley (1999), Geneva (2000), Berkeley (2001), Harvard (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). Topics of interest for APPROX and RANDOM are: design and analysis of - proximation algorithms, hardness of approximation, small space, sub-linear time, streaming, algorithms, embeddings and metric space methods, mathematical programming methods, combinatorial problems in graphs and networks, game t- ory, markets, economic applications, geometric problems, packing, covering, scheduling, approximate learning, design and analysis of randomized algorithms, randomized complexity theory, pseudorandomness and derandomization, random combinatorial structures, random walks/Markov chains, expander graphs and randomness extractors, probabilistic proof systems, random projections and - beddings, error-correcting codes,average-case analysis, property testing, com- tational learning theory, and other applications of approximation and randomness.

This book constitutes the refereed proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008, held in Torun, Poland, in August 2008. The 45 revised full papers presented together with 5 invited lectures were carefully reviewed and selected from 119 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithmic game theory, algorithms and data structures, artificial intelligence, automata and formal languages, bioinformatics, complexity, concurrency and petrinets, cryptography and security, logic and formal specifications, models of computations, parallel and distributed computing, semantics and verification.

This book constitutes the refereed proceedings of the First Annual International Frontiers of Algorithmics Workshop, FAW 2007, held in Lanzhou, China in August 2007. Topics covered in the papers include bioinformatics, discrete structures, geometric information processing and communication, games and incentive analysis, graph algorithms, internet algorithms and protocols, and algorithms in medical applications.

This book constitutes the refereed proceedings of the 10th International Workshop on Computer Algebra in Scientific Computing, CASC 2007, held in Bonn, Germany, in September 2007. The volume is dedicated to Professor Vladimir P. Gerdt on the occasion of his 60th birthday. The papers cover not only various expanding applications of computer algebra to scientific computing but also the computer algebra systems themselves and the CA algorithms.

This book constitutes the refereed proceedings of the 17th International Symposium on Algorithms and Computation, ISAAC 2006, held in Kolkata, India, December 2006. The 73 revised full papers cover algorithms and data structures, online algorithms, approximation algorithm, computational geometry, computational complexity, optimization and biology, combinatorial optimization and quantum computing, as well as distributed computing and cryptography.

Here are the refereed proceedings of the 6th International Workshop on Algorithms in Bioinformatics, WABI 2006, held in the course of the ALGO 2006 conference meetings. The book presents 36 revised full papers addressing all current issues of algorithms in bioinformatics, from mathematical tools to experimental studies of approximation algorithms and reports on significant computational analyses. For the first time, coverage extends to machine-learning approaches along with combinatorial optimization.

This book constitutes the refereed proceedings of the 5th Workshop on Algorithm Engineering, WAE 2001, held in Aarhus, Denmark, in August 2001. The 15 revised full papers presented were carefully reviewed and selected from 25 submissions. Among the topics addressed are implementation, experimental testing, and fine-tuning of discrete algorithms; novel use of discrete algorithms in other disciplines; empirical research on algorithms and data structures; and methodological issues regarding the process of converting user requirements into efficient algorithmic solutions and implemenations.

This book constitutes the joint refereed proceedings of the 4th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2001 and of the 5th International Workshop on Ranomization and Approximation Techniques in Computer Science, RANDOM 2001, held in Berkeley, California, USA in August 2001. The 26 revised full papers presented were carefully reviewed and selected from a total of 54 submissions. Among the issues addressed are design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization, de-randomization, average-case analysis, approximation classes, randomized complexity theory, scheduling, routing, coloring, partitioning, packing, covering, computational geometry, network design, and applications in various fields.

This volume contains the 74 contributed papers and abstracts of 4 of the 5 invited talks presented at the 10th Annual European Symposium on Algorithms (ESA 2002), held at the University of Rome “La Sapienza”, Rome, Italy, 17-21 September, 2002. For the?rst time, ESA had two tracks, with separate program committees, which dealt respectively with: – the design and mathematical analysis of algorithms (the “Design and An- ysis” track); – real-world applications, engineering and experimental analysis of algorithms (the “Engineering and Applications” track). Previous ESAs were held in Bad Honnef, Germany (1993); Utrecht, The Neth- lands (1994); Corfu, Greece (1995); Barcelona, Spain (1996); Graz, Austria (1997); Venice, Italy (1998); Prague, Czech Republic (1999); Saarbruc ¨ ken, Ger-? many (2000), and Arhus, Denmark (2001). The predecessor to the Engineering and Applications track of ESA was the Annual Workshop on Algorithm En- neering (WAE). Previous WAEs were held in Venice, Italy (1997), Saarbruc ¨ ken,? Germany (1998), London, UK (1999), Saarbru ¨cken, Germany (2000), and Arhus, Denmark (2001). The proceedings of the previous ESAs were published as Springer LNCS volumes 726, 855, 979, 1284, 1461, 1643, 1879, and 2161. The proceedings of WAEs from 1999 onwards were published as Springer LNCS volumes 1668, 1982, and 2161.

The Complexity Theory Companion is an accessible, algorithmically oriented, research-centered, up-to-date guide to some of the most interesting techniques of complexity theory.The book's thesis is that simple algorithms are at the heart of complexity theory. From the tree-pruning and interval-pruning algorithms that shape the first chapter to the query simulation procedures that dominate the last chapter, the central proof methods of the book are algorithmic. And to more clearly highlight the role of algorithmic techniques in complexity theory, the book is - unlike other texts on complexity - organized by technique rather than by topic. Each chapter of this book focuses on one technique: what it is, and what results and applications it yields. This textbook was developed at the University of Rochester in courses given to graduate students and advanced undergraduates. Researchers also will find this book a valuable source of reference due to the comprehensive bibliography of close to five hundred entries, the thirty-five page subject index, and the appendices giving overviews of complexity classes and reductions.

Graph algorithms is a well-established subject in mathematics and computer science. Beyond classical application fields, like approximation, combinatorial optimization, graphics, and operations research, graph algorithms have recently attracted increased attention from computational molecular biology and computational chemistry. Centered around the fundamental issue of graph isomorphism, this text goes beyond classical graph problems of shortest paths, spanning trees, flows in networks, and matchings in bipartite graphs. Advanced algorithmic results and techniques of practical relevance are presented in a coherent and consolidated way. This book introduces graph algorithms on an intuitive basis followed by a detailed exposition in a literate programming style, with correctness proofs as well as worst-case analyses. Furthermore, full C++ implementations of all algorithms presented are given using the LEDA library of efficient data structures and algorithms. Numerous illustrations, examples, and exercises, and a comprehensive bibliography support students and professionals in using the book as a text and source of reference

An Invitation to the Dance It is an underappreciated fact that sets may have various types of complex­ ity, and not all types are in harmony with each other. The primary goal of this book is to unify and make more widely accessible a vibrant stream of research-the theory of semi-feasible computation-that perfectly showcases the richness of, and contrasts between, the central types of complexity. The semi-feasible sets, which are most commonly referred to as the P­ selective sets, are those sets L for which there is a deterministic polynornial­ time algorithm that, when given as input any two strings of which at least one belongs to L, will output one of them that is in L. The reason we saythat the semi-feasible sets showcase the contrasts among types of complexity is that it is well-known that many semi-feasible sets have no recursive algorithms (thus their time complexitycannot be upper-bounded by standard time-complexity classes), yet all semi-feasible sets are simple in a wide range of other natural senses. In particular, the semi-feasible sets have small circuits, they are in the extended low hierarchy, and they cannot be NP-complete unless P = NP. The semi-feasible sets are fascinating for many reasons. First, as men­ tioned above, they showcase the fact that mere deterministic time complex­ ity is not the only potential type of complexity in the world of computation.

For a long time computer scientists have distinguished between fast and slow algo rithms. Fast (or good) algorithms are the algorithms that run in polynomial time, which means that the number of steps required for the algorithm to solve a problem is bounded by some polynomial in the length of the input. All other algorithms are slow (or bad). The running time of slow algorithms is usually exponential. This book is about bad algorithms. There are several reasons why we are interested in exponential time algorithms. Most of us believe that there are many natural problems which cannot be solved by polynomial time algorithms. The most famous and oldest family of hard problems is the family of NP complete problems. Most likely there are no polynomial time al gorithms solving these hard problems and in the worst case scenario the exponential running time is unavoidable. Every combinatorial problem is solvable in?nite time by enumerating all possi ble solutions, i. e. by brute force search. But is brute force search always unavoid able? De?nitely not. Already in the nineteen sixties and seventies it was known that some NP complete problems can be solved signi?cantly faster than by brute force search. Three classic examples are the following algorithms for the TRAVELLING SALESMAN problem, MAXIMUM INDEPENDENT SET, and COLORING.