Combinatorial optimization and graph algorithms : communications of NII Shonan Meetings /: communications of NII Shonan Meetings. (2017)

• Record Type: Book
• Further Information: Note: Takuro Fukunaga, Ken-ichi Kawarabayashi, editors.
• Editors: Fukunaga, Takuro; Kawarabayashi, Ken-ichi
• Contents: ""Preface""; ""Contents""; ""Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems""; ""1 Introduction""; ""2 Local Search Algorithms""; ""2.1 Uncapacitated Facility Location""; ""2.2 Capacitated Facility Location""; ""2.3 k-median and k-means""; ""3 LP-Based Algorithms""; ""3.1 LP-Rounding for Facility Location""; ""3.2 Primal-Dual Algorithms for Facility Location""; ""3.3 k-median and Its Relaxations""; ""3.4 Capacitated Problems""; ""4 Future Directions""; ""References""; ""Graph Stabilization: A Survey""; ""1 Introduction""; ""1.1 Definitions"" ""2 Characterizing Stable Graphs""""3 Edge Modifications""; ""3.1 Edge Deletion""; ""3.2 Edge Addition""; ""4 Vertex Modifications""; ""4.1 Vertex Deletion""; ""4.2 Min Cost Vertex Deletion""; ""4.3 Vertex Addition""; ""5 Edge Weight Addition""; ""6 Further Open Problems""; ""References""; ""Spider Covering Algorithms for Network Design Problems""; ""1 Introduction""; ""1.1 Organization""; ""2 Preliminaries""; ""3 Spider Covering Algorithm for the Node-Weighted Steiner Tree""; ""4 LP-Based Analysis of the Spider Covering Algorithm""; ""5 Node-Weighted Edge-Connectivity Network Design"" ""6 Node-Connectivity Network Activation Problem""""7 Other Applications""; ""7.1 Prize-Collecting Network Design Problems""; ""7.2 Buy-at-bulk Network Design Problems""; ""7.3 Directed Steiner Tree and Forest Problems""; ""7.4 Online Network Design Problems""; ""8 Conclusion""; ""References""; ""Discrete Convex Functions on Graphs and Their Algorithmic Applications""; ""1 Introduction""; ""2 L-Convex Function on Grid-Like Structure""; ""2.1 L-Convex Function on Tree-Grid""; ""2.2 L-Convex Function on Twisted Tree-Grid""; ""2.3 Steepest Descent Algorithm"" ""2.4 L-Convex Function on Euclidean Building""""3 Application""; ""3.1 Minimum-Cost Multiflow and Terminal Backup""; ""3.2 Node-Capacitated Multiflow and Node-Multiway Cut""; ""4 L-Convex Function on Oriented Modular Graph""; ""4.1 Motivation: Minimum 0-Extension Problem""; ""4.2 Submodular Function on Modular Semilattice""; ""4.3 L-Convex Function on Oriented Modular Graph""; ""References""; ""Parameterized Complexity of the Workflow Satisfiability Problem""; ""1 Introduction""; ""1.1 The Workflow and Constraint Satisfiability Problems""; ""1.2 Parameterized Complexity Approach to WSP"" ""2 Background""""2.1 Constraints and Authorization Lists""; ""2.2 Complexity of WSP""; ""2.3 Fixed-Parameter Tractability and WSP""; ""3 Fixed-Parameter Tractability Results""; ""3.1 Regular Constraints""; ""3.2 User-Independent Constraints""; ""3.3 Class-Independent Constraints""; ""4 Characterizing the FPT Languages""; ""4.1 Equivalent Partial Solutions and a Diversity Measure""; ""5 Classical Tractable Conservative Constraint Languages""; ""6 Concluding Remarks""
• Publisher Details: Singapore : Springer
• Publication Date: 2017
• Extent: 1 online resource, illustrations
• Subjects: 511.6; Combinatorial optimization; Graph algorithms; Graph theory; Computer algorithms; MATHEMATICS -- General; Combinatorial optimization; Computer algorithms; Graph algorithms; Graph theory; Computer Science; Discrete Mathematics in Computer Science; Discrete Mathematics; Operations Research/Decision Theory; Electronic books; Electronic book
• Languages: English
• ISBNs: 9789811061479; 9811061475
• Related ISBNs: 9789811061462; 9811061467
• Notes: Note: Includes bibliographical references.; Note: Online resource; title from PDF title page (EBSCO, viewed October 16, 2017).
• 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.