Ding-Zhu Du

Xiang-Sun Zhang

Algorithms and Computation

Ker-I Ko

This book contains a collection of survey papers in the areas of algorithms, lan guages and complexity, the three areas in which Professor Ronald V. Book has made significant contributions. As a fonner student and a co-author who have been influenced by him directly, we would like to dedicate this book to Professor Ronald V. Book to honor and celebrate his sixtieth birthday. Professor Book initiated his brilliant academic career in 1958, graduating from Grinnell College with a Bachelor of Arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. Professor Book's research in discrete mathematics and theoretical com puter science is reflected in more than 150 scientific publications. These works have made a strong impact on the development of several areas of theoretical computer science. A more detailed summary of his scientific research appears in this volume separately.

Advances in Algorithms, Languages, and Complexity

Dachuan Xu

Donglei Du

Chenchen Wu

This book constitutes the refereed proceedings of the 17th Annual Conference on Theory and Applications of Models of Computation, TAMC 2022, held as a virtual event, in September 2022. The 33 full papers were carefully reviewed and selected from 75 submissions. The main themes of the selected papers are computability, complexity, algorithms, information theory and their extensions to machine learning theory, and foundations of artificial intelligence.

17th Annual Conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings

Theory and Applications of Models of Computation

F. Hsu

A basic problem for the interconnection of communications media is to design interconnection networks for specific needs. For example, to minimize delay and to maximize reliability, networks are required that have minimum diameter and maximum connectivity under certain conditions. The book provides a recent solution to this problem. The subject of all five chapters is the interconnection problem. The first two chapters deal with Cayley digraphs which are candidates for networks of maximum connectivity with given degree and number of nodes. Chapter 3 addresses Bruijn digraphs, Kautz digraphs, and their generalizations, which are candidates for networks of minimum diameter and maximum connectivity with given degree and number of nodes. Chapter 4 studies double loop networks, and Chapter 5 considers broadcasting and the Gossiping problem. All the chapters emphasize the combinatorial aspects of network theory. Audience: A vital reference for graduate students and researchers in applied mathematics and theoretical computer science.

Combinatorial Network Theory

Xiaohua Jia

Xiao-Dong Hu

Multiwavelength Optical Networks systematically studies the major research issues in WDM (Wavelength Division Multiplexing) optical networks, such as routing and wavelength assignment, QoS multicast routing, design of logical topologies, and placement of wavelength converters. The book consists of two parts. The first part studies the fundamental concepts and principles of WDM networks. The second part discusses advanced and research issues of WDM networks. The authors of the book have many years of working experience in the areas of computer networks and network optimization. The book discusses many difficult issues of WDM networks in a very comprehensive way. For each problem, there is a background discussion, and then the mathematical formulation, followed by the solutions.

Multiwavelength Optical Networks

Xiaoming Sun

Lian Li

Jialin Zhang

This volume constitutes the proceedings of the 13th International Conference on Algorithmic Aspects in Information and Management, AAIM 2019, held in Bejing, China in August 2019. The 31 full papers presented were carefully reviewed and selected. The papers deal with most aspects of theoretical computer science and their applications. Special considerations are given to algorithmic research that is motivated by real-world applications.

13th International Conference, AAIM 2019, Beijing, China, August 6–8, 2019, Proceedings

Algorithmic Aspects in Information and Management

Jie Wang

This Festschrift is in honor of Ker-I Ko, Professor in the Stony Brook University, USA. Ker-I Ko was one of the founding fathers of computational complexity over real numbers and analysis. He and Harvey Friedman devised a theoretical model for real number computations by extending the computation of Turing machines. He contributed significantly to advancing the theory of structural complexity, especially on polynomial-time isomorphism, instance complexity, and relativization of polynomial-time hierarchy. Ker-I also made many contributions to approximation algorithm theory of combinatorial optimization problems. This volume contains 17 contributions in the area of complexity and approximation. Those articles are authored by researchers over the world, including North America, Europe and Asia. Most of them are co-authors, colleagues, friends, and students of Ker-I Ko.

In Memory of Ker-I Ko

Complexity and Approximation

Xiuzhen Cheng

This book is a collection of 16 state-of-the-art articles contributed by the most influential experts in the field of Steiner tree applications. The articles are designed to explore the impact on industries of the long-term theoretical development of Steiner tree problems. The authors address various Steiner tree problems originating from and applied to industry fields, such as the design of electronic circuits, telecommunication networks, computer networks, and computer biology. This book is a good reference tool for scientists who depend on Steiner tree problems in some way. Audience: Researchers in computer science, mathematics, and electrical engineering, as well as students. This book is suitable for both specialists and uniformed readers.

Steiner Trees in Industry

Xiao Huang

Wireless networking enables two or more computers to communicate using standard network protocols without network cables. Since their emergence in the 1970s, wireless networks have become increasingly pop ular in the computing industry. In the past decade, wireless networks have enabled true mobility. There are currently two versions of mobile wireless networks. An infrastructure network contains a wired backbone with the last hop being wireless. The cellular phone system is an exam ple of an infrastructure network. A multihop ad hoc wireless network has no infrastructure and is thus entirely wireless. A wireless sensor network is an example of a multihop ad hoc wireless network. Ad hoc wireless networking is a technique to support robust and ef ficient operation in mobile wireless networks by incorporating routing functionality into mobile hosts. This technique will be used to realize the dream of "anywhere and anytime computing", which is termed mo bile computing. Mobile computing is a new paradigm of computing in which users carrying portable devices have access to shared infrastruc ture in any location at any time. Mobile computing is a very challenging topic for scientists in computer science and electrical engineering. The representative system for ad hoc wireless networking is called MANET, an acronym for "Mobile Ad hoc NETworks". MANET is an autonomous system consisting of mobile hosts connected by wireless links which can be quickly deployed.

Ad Hoc Wireless Networking

Sajal K. Das

Yingshu Li

Dung T. Huynh

Recent advances in cutting-edge wireless communication and computing te- nologies have paved the way for the proliferation of ubiquitous infrastructure and infrastructureless wireless networks. These emerging networks are enabling a broad spectrum of applications ranging from critical infrastructure prot- tion and security, to environment monitoring, health care, and quality of life. The need to deal with the complexity and rami?cations of the ever-growing mobile users and services, however, is intensifying the interest in the devel- ment of sound fundamental principles, novel algorithmic approaches, rigorous and repeatable design methodologies, and systematic evaluation frameworks for next-generation wireless networks. The Third International Conference on Wireless Algorithms, Systems and Applications (WASA) was held in Dallas, TX, USA during October 26–28. The objective of WASA is to address the research and development e?orts of va- ous issues in the area of algorithms, systems and applications for current and next-generationinfrastructureandinfrastructurelesswirelessnetworks. Thec- ference is structured to provide a forum for researchers and practitioners, from the academic, industrial, and governmental sectors, with a unique opportunity to discussandexpresstheirviews onthe currenttrends,challenges,andstate-- the-artsolutionsaddressingvariousissuesrelatedtocurrentandnext-generation wireless networks. Following a rigorous review process, the Program Committee selected an outstanding set of 35 papers for publication in the proceedings and oral presentations at the conference. The program of WASA 2008 also included three keynote talks by Lionel Ni, Ty Znati, and Jie Wu along with 15 invited papers.

Third International Conference, WASA 2008, Dallas, TX, USA, October 26-28, 2008, Proceedings

Wireless Algorithms, Systems, and Applications

This volume is the proceedings of the fifth International Symposium on Algorithms and Computation, ISAAC '94, held in Beijing, China in August 1994. The 79 papers accepted for inclusion in the volume after a careful reviewing process were selected from a total of almost 200 submissions. Besides many internationally renowned experts, a number of excellent Chinese researchers present their results to the international scientific community for the first time here. The volume covers all relevant theoretical and many applicational aspects of algorithms and computation.

5th International Symposium, ISAAC '94, Beijing, P.R. China, August 25 - 27, 1994. Proceedings

Hung Q. Ngo

This book contains recent developments in switching networks and applications, including classic topics, such as nonblocking and Benes conjecture, and new directions, such as optical switching networks and applications in VLSI designs. It provides the state of the art for researchers in computer networks and applied mathematics. Audience: Researchers in computer networks and applied mathematics. The book is appropriate for use in graduate courses.

Switching Networks: Recent Advances

A complete treatment of fundamentals and recent advances in complexity theory Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form. Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the application to cryptography. It also examines the theory of nonuniform computational complexity, including the computational models of decision trees and Boolean circuits, and the notion of polynomial-time isomorphism. The theory of probabilistic complexity, which studies complexity issues related to randomized computation as well as interactive proof systems and probabilistically checkable proofs, is also covered. Extraordinary in both its breadth and depth, this volume: * Provides complete proofs of recent breakthroughs in complexity theory * Presents results in well-defined form with complete proofs and numerous exercises * Includes scores of graphs and figures to clarify difficult material An invaluable resource for researchers as well as an important guide for graduate and advanced undergraduate students, Theory of Computational Complexity is destined to become the standard reference in the field.

Theory of Computational Complexity

Panos M. Pardalos

Xiaodong Hu

This book constitutes the refereed proceedings of the Third International Conference on Combinatorial Optimization and Applications, COCOA 2009, held in Huangshan, China, in June 2009. The 50 revised full papers were carefully reviewed and selected from 103 submissions. The papers feature original research in the areas of combinatorial optimization - both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.

Third International Conference, COCOA 2009, Huangshan, China, June 10-12, 2009, Proceedings

Combinatorial Optimization and Applications

Azer Bestavros

Benyuan Liu

Systems.” The workshop consisted of seven papers selected by the Program Committee of the workshop, chaired by Guanling Chen and Wei Ding.

4th International Conference, WASA 2009, Boston, MA, USA, August 16-18, 2009, Proceedings

This book constitutes the refereed proceedings of the 15th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2021, which took place in Tianjin, China, during December 17-19, 2021. The 55 papers presented in this volume were carefully reviewed and selected from 122 submissions. They deal with combinatorial optimization and its applications in general, focusing on algorithms design, theoretical and experimental analysis, and applied research of general algorithmic interest.

15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings

Peng-Jun Wan

This book reviews problems in connected dominating set theory, discussing motivation and overview, problem complexity analysis and approximation algorithm designs. Readers will clearly grasp background, formulation, major research results and open problems.

Theory and Applications

Connected Dominating Set

Boting Yang

Cao An Wang

This book constitutes the refereed proceedings of the Second International Conference on Combinatorial Optimization and Applications, COCOA 2008, held in St. John's, Canada, in August 2008. The 44 revised full papers were carefully reviewed and selected from 84 submissions. The papers feature original research in the areas of combinatorial optimization -- both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.

Second International Conference, COCOA 2008, St. John's, NL, Canada, August 21-24, 2008, Proceedings

Bin Fu

This book constitutes the refereed proceedings of the 17th Annual International Conference on Computing and Combinatorics, held in Dallas, TX, USA, in August 2011. The 54 revised full papers presented were carefully reviewed and selected from 136 submissions. Topics covered are algorithms and data structures; algorithmic game theory and online algorithms; automata, languages, logic, and computability; combinatorics related to algorithms and complexity; complexity theory; computational learning theory and knowledge discovery; cryptography, reliability and security, and database theory; computational biology and bioinformatics; computational algebra, geometry, and number theory; graph drawing and information visualization; graph theory, communication networks, and optimization; parallel and distributed computing.

17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings

Computing and Combinatorics

This book is a collection of articles studying various Steiner tree prob lems with applications in industries, such as the design of electronic cir cuits, computer networking, telecommunication, and perfect phylogeny. The Steiner tree problem was initiated in the Euclidean plane. Given a set of points in the Euclidean plane, the shortest network interconnect ing the points in the set is called the Steiner minimum tree. The Steiner minimum tree may contain some vertices which are not the given points. Those vertices are called Steiner points while the given points are called terminals. The shortest network for three terminals was first studied by Fermat (1601-1665). Fermat proposed the problem of finding a point to minimize the total distance from it to three terminals in the Euclidean plane. The direct generalization is to find a point to minimize the total distance from it to n terminals, which is still called the Fermat problem today. The Steiner minimum tree problem is an indirect generalization. Schreiber in 1986 found that this generalization (i.e., the Steiner mini mum tree) was first proposed by Gauss.

Ding-Zhu Du

About

Books

Join the club