Additive Cellular Automata on Graphs

Erscheinungsjahr 2027
ISBN: 978-3-032-47284-7
Verlag: Springer

Buch, Englisch, Format (B × H): 155 mm x 235 mm

Reihe: SpringerBriefs in Mathematics

This volume surveys the phenomenon of cellular automata, discrete dynamical systems consisting of an arrangement of basic components called cells together with a transition rule. The term was introduced by John von Neumann as a formal model for self-reproducing biological systems.

The authors of this volume highlight the study of automaton in biparte graphs and conduct an in-depth investigation into the minimum all-ones problem within the context of trees. While this problem is NP-hard for graphs, the authors manage to solve it in linear time when it comes to trees. They further present linear time algorithms for the minimum all-ones problem of unicyclic and bicyclic graphs.

Additionally, the authors study general all-ones problems for trees, and present all-colors problems on graphs. They go on to report on several variations of all-ones problems on graphs and on approximation algorithms for the minimum all-ones problem of arbitrary graphs. Throughout the volume, the authors list conjectures, open problems, and questions.

This volume proves inspirational for young graph theorists and graduate students to conduct further research and provide them with select proofs common in the study of cellular automata on graphs.

Zielgruppe

Research

Autoren/Hrsg.

Zhang, Xiaoyan

Wang, Chao

Li, Xueliang

Mao, Yaping

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

Introduction.- $\sigma$ Automation on Bipartite Graphs.- $\sigma^{+}All-Ones Problem on Trees.- Linear Time Algorithms for the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs.- The General $\sigma$ All-Ones Problem for Trees.- All-Colors Problems on Graphs.- Several Kinds of Variations of All-Ones Problems on Graphs.- Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs.

Über Autor(innen)

Xiaoyan Zhang received the first Ph.D. degree in Applied Mathematics from Nankai University in 2006 and received the second Ph.D. degree in Computer Science from Twente University in 2014. He is currently a full professor in Ministry of Education Key Laboratory of NSLSCS, Institute of Mathematics and School of Mathematical Sciences, Nanjing Normal University. He has published more than 70 academic papers in reputable journals such as SIAM J. Computing, SIAM J. Scientific Computing, SIAM J. Discrete Math,  IEEE Transactions on Computers and IEEE Transactions on Information Theory. His major research interest includes efficient algorithm design and computational complexity analysis, particularly for combinatorial optimization, graph algorithms, VLSI circuit design and networks, etc. 

Chao Wang received his Ph.D. degree in Applied Mathematics from Nankai University in 2003. He is currently an associate researcher at School of Software, Nankai University. He has published more than 30 academic papers in well-known journals such as SIAM J. Computing, Information Sciences, and Applied Mathmatical Computation. His research interests include applied mathematics, theoretical computer science, especially cellular automata and image enhancement.

Xueliang Li received his PhD degree in Discrete Mathematics from University of Twente, the Netherlands in 1991. He is a distinguished professor and a co-director of the Center for Combinatorics, Nankai University, China. He was elected as a member in 2011 and a Vice-President of the International Academy of Mathematical Chemistry in 2014 and 2023. He works mainly in graph theory and combinatorial optimizations, chemical graph theory, and has published more than 300 papers in reputable international journals, and more than 10 books. From 2021 through 2024, he was on the Elsevier list of Most Cited Chinese Researchers. In 2023, he was on the list of Top 100-Thousand-Scientists on the Global Ranking List for Academic Influence (Life-Time Academic Influence) (made by Database of Global Scientists). In 2024, he is on the list of the World’s Top 2% Scientists (made by Stanford University). He has trained more than 80 PhD students and more than 30 MSc students. More than 10 Postdoctors have worked with him. He is an editorial member for more than 10 international journals, including Discrete Applied Mathematics (Elsevier), Journal of Mathematical Chemistry (Springer), Graphs and Combinatorics (Springer), and Acta Mathematicae Applicatae Sinica (Springer).

Yaping Mao is a professor of mathematics in the School of Mathematics and Statistics at Qinghai Normal University, China. He served as Vice Dean of the school from 2017 to 2021. Professor Mao earned his Ph.D. in Applied Mathematics from Nankai University (China) in 2014. Professor Mao has directed over 20 graduate students in research projects. He got the Chebyshev grant from ICM and JSPS grant from Japan. He is one of directors of Chinese Mathematical Society and the president of Qinghai Mathematical Society. He has published one book and over 80 academic research papers. Currently, he is on the editorial team for of a number of journals, such as International Journal of Interactive Multimedia and Artificial Intelligence (UNIV INT RIOJA-UNIR), Parallel Processing Letters (World Scientific), Journal of Interconnection Networks (World Scientific), International Journal of Computer Mathematics: Computer Systems Theory (Taylor Francis), Theory and Applications of Graphs (Georgia Southern University), Algebra Combinatorics, Discrete Structures and Applications (Jacodesmath Institute).