Frontiers in Algorithmics
14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings
Published on 22. September 2020
IX, 145 pages
978-3-030-59901-0 (ISBN)
Description
This book constitutes the proceedings of the 14th International Workshop on Frontiers in Algorithmics, FAW 2020, held in Haikou, China, in May 2020. The conference was held virtually due to the COVID-19 pandemic. The 12 full papers presented in this volume were carefully reviewed and selected from 15 submissions.
The workshop provides a focused forum on current trends of research on algorithms, discrete structures, and their applications, and brings together international experts at the research frontiers in these areas to exchange ideas and to present significant new results. The papers detail graph theory, scheduling and algorithm and complexity.
The workshop provides a focused forum on current trends of research on algorithms, discrete structures, and their applications, and brings together international experts at the research frontiers in these areas to exchange ideas and to present significant new results. The papers detail graph theory, scheduling and algorithm and complexity.
More details
Series
Edition
1st ed. 2020
Language
English
Place of publication
Cham
Switzerland
Publishing group
Springer International Publishing
Product notice
Reflowable
Illustrations
IX, 145 p. 51 illus., 2 illus. in color.
ISBN-13
978-3-030-59901-0 (9783030599010)
DOI
10.1007/978-3-030-59901-0
Schweitzer Classification
Other editions
Additional editions
Minming Li
Frontiers in Algorithmics
14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings
Book
09/2020
Springer
€53.49
Shipment within 7-9 days
Content
- Intro
- Preface
- Organization
- Contents
- Complexity Results for the Proper Disconnection of Graphs
- 1 Introduction
- 2 Hardness Results for Graphs with Maximum Degree Four
- 3 Hardness Results for Bipartite Graphs
- References
- A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs
- 1 Introduction
- 2 Preliminary
- 2.1 Graphs and Notations
- 2.2 Enumeration Algorithms
- 3 Family Tree of 2-Edge-Connected Induced Subgraphs
- 4 Enumeration Algorithm
- References
- An Optimal Algorithm for Bisection for Bounded-Treewidth Graph
- 1 Introduction
- 2 Preliminaries
- 3 Bounded-Treewidth Graphs
- 3.1 An O(2tn3)-Time Algorithm
- 3.2 A Refined Analysis for Join Nodes
- 3.3 Optimality of Our Algorithm
- 4 Hardness on Graph Classes
- 5 Line Graphs
- 6 Conclusion
- References
- Influence Maximization Under the Non-progressive Linear Threshold Model
- 1 Introduction
- 2 Preliminaries
- 3 Hardness of Maximization Problem
- 4 Acyclic Information Networks
- 4.1 Connection to the Random Walk
- 4.2 Submodularity of Acyclic NLT
- 5 Conclusions
- References
- Car-Sharing: Online Scheduling k Cars Between Two Locations
- 1 Introduction
- 1.1 Related Work
- 1.2 Problem Description and Preliminaries
- 1.3 Main Results
- 2 Lower Bounds
- 3 Upper Bounds
- 3.1 Greedy Dispatching (GD) Algorithm
- 3.2 Balanced Dispatching (BD)
- 4 Conclusions
- References
- Buffer Minimization with Conflicts on a Line
- 1 Introduction
- 1.1 Overview of Results
- 1.2 Related Literature
- 2 Definitions
- 3 The Competitive Ratio of the Path with Four Machines
- 4 Bounds on the Competitive Ratio for Five Machines
- 5 Results on m Machines
- References
- Single Machine Scheduling Problem with a Flexible Maintenance Revisited
- 1 Introduction
- 2 The Exact Worst-Case Bound
- 3 Initial Start Time Sensitivity Analysis
- References
- Minimizing Energy on Homogeneous Processors with Shared Memory
- 1 Introduction
- 2 Preliminaries
- 2.1 System and Task Model
- 2.2 Problem Definition
- 3 Warm-Up: Single Core Case
- 4 Multi-core Case
- 4.1 Computing Optimal Schedule for a Given Task Assignment
- 4.2 Task Assignment
- References
- Approximation Schemes for Subset Sum Ratio Problems
- 1 Introduction
- 2 Families of Variations of SSR
- 3 A Framework Yielding FPTAS for Problems in F-SSR
- 4 2-Set SSR
- 5 Approximation of SSR and Factor-r SSR
- References
- Two-Way Jumping Automata
- 1 Introduction
- 2 Preliminaries
- 2.1 Tape Head Modes
- 3 Two-Way Jumping Mode
- 4 Equivalence with Alternatively Defined RLDFA
- 5 Avoiding Infinite Loops
- References
- A Loopless Algorithm for Generating (k,m)-ary Trees in Gray-Code Order
- 1 Introduction
- 2 Preliminaries
- 3 A Loopless Algorithm
- 4 Concluding Remarks
- References
- An LP-Rounding Based Algorithm for a Uniform Capacitated Facility Location Problem with Penalties
- 1 Introduction
- 1.1 Background
- 1.2 Literature Reviews
- 2 Preliminaries
- 2.1 Problem Statement
- 2.2 Single Node Capacitated Facility Location Problem
- 3 Algorithm and Analysis
- 3.1 Clustering
- 3.2 Opening Facilities
- 3.3 Connecting Customers
- 4 Conclusions
- References
- Author Index
