Frontiers in Algorithmics

Name: Frontiers in Algorithmics | 14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings

Minming Li(Herausgeber*in)

Springer (Verlag)

Erschienen am 22. September 2020

IX, 145 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-59901-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken