Frontiers in algorithmics : 14th international conference, FAW 2020, Haikou, China, October 19-21, 2020, proceedings /: 14th international conference, FAW 2020, Haikou, China, October 19-21, 2020, proceedings. (2020)

• Record Type: Book
• Other Titles: FAW 2020
• Further Information: Note: Minming Li (ed.).
• Editors: Li, Minming
• Other Names: International Frontiers of Algorithmics Workshop, 14th
• Contents: 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
• Publisher Details: Cham : Springer
• Publication Date: 2020
• Copyright Date: 2020
• Extent: 1 online resource (145 pages)
• Subjects: 005.1; Computer algorithms -- Congresses; Computer science; Algorithms & data structures; Computer networking & communications; Discrete mathematics; Computers -- Computer Science; Computers -- Information Theory; Computers -- Networking -- General; Computers -- Data Processing; Computer algorithms; Electronic books; Electronic books; Conference papers and proceedings
• Languages: English
• ISBNs: 9783030599010
• Related ISBNs: 9783030599003
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.