Graph-theoretic concepts in computer science : 43rd International Workshop, WG 2017, Eindhoven, the Netherlands, June 21-23, 2017, Revised selected papers / Hans L. Bodlaender, Gerhard J. Woeginger (eds.).
Contributor(s): Bodlaender, H. L [editor.] | Woeginger, Gerhard [editor.]Material type: TextSeries: SerienbezeichnungLecture notes in computer science: 10520.; Lecture notes in computer science: ; LNCS sublibrary: Publisher: Cham, Switzerland : Springer, 2017Description: 1 online resource (xiii, 440 pages) : illustrationsContent type: text Media type: computer Carrier type: online resourceISBN: 9783319687056; 3319687050Other title: WG 2017Subject(s): Graph theory -- Data processing -- Congresses | Computer science -- Mathematics -- Congresses | Computers -- Programming -- Algorithms | Computers -- Data Modeling & Design | Computers -- Computer Graphics | Mathematics -- Geometry -- General | Algorithms & data structures | Graphics programming | Geometry | Numerical analysis | Computers -- Data Processing | Discrete mathematics | Computer science -- Mathematics | Graph theory -- Data processingGenre/Form: Electronic books. | Conference papers and proceedings. Additional physical formats: Printed edition:: No titleDDC classification: 004.01/51 LOC classification: QA166Online resources: Click here to access online
|Item type||Current location||Collection||Call number||Status||Date due||Barcode||Item holds|
Includes author index.
Online resource; title from PDF title page (SpringerLink, viewed November 9, 2017).
This book constitutes the revised selected papers of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, held in Eindhoven, The Netherlands, in June 2017. The 31 full papers presented in this volume were carefully reviewed and selected from 71 submissions. They cover a wide range of areas, aiming at connecting theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. Another focus is on presenting recent results and on identifying and exploring promising directions of future research.
Intro; Preface; Organization; Contents; Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions; 1 Complex Networks and Random Graphs: A Motivation; 2 Random Graphs and Real-World Networks; 3 Random Graph Models as Null Models; 3.1 Null Model 1: Uniform Random Graph; 3.2 Null Model 2: Erdős-Rényi Random Graph with Fixed Number of Edges; 3.3 Null Model 3: Fixing All Degrees and the Configuration Model; 3.4 Small-World Properties of the Configuration Model; 4 Extensions: Other Models; References; On Bubble Generators in Directed Graphs; 1 Introduction.
2 Preliminaries3 The Bubble Generator; 4 A Polynomial-Time Algorithm for Decomposing a Bubble; 5 Conclusions and Open Problems; References; Critical Node Cut Parameterized by Treewidth and Solution Size is W-Hard; 1 Introduction; 2 Preliminaries; 3 W-HardNess of SumCSP; 4 W-HardNess of CNC; References; Hierarchical Partial Planarity; 1 Introduction; 2 Preliminaries; 3 Relationships to Other Planarity Problems; 4 Biconnected Facial-Constrained Core Planarity; 4.1 High-Level Description of the Algorithm; 4.2 Detailed Description of the Algorithm; 5 Open Problems; References.
On the Relationship Between k-Planar and k-Quasi-Planar Graphs1 Introduction; 2 Preliminaries; 3 Edge Rerouting Operations and Proof Strategy; 4 Removing Tangled (k+1)-Crossings; 5 Removing Untangled (k+1)-Crossings; 5.1 Obtaining (k+1)-Quasi-Planarity; 5.2 Obtaining Simplicity; 6 Conclusions and Open Problems; References; Extension Complexity of Stable Set Polytopes of Bipartite Graphs; 1 Introduction; 2 Rectangle Covers and Fooling Sets; 3 An Improved Upper Bound; 4 An Improved Lower Bound; 5 A Small Rectangle Cover of the Special Entries; References.
On the Number of Labeled Graphs of Bounded Treewidth1 Introduction; 2 The Construction; 2.1 Notation and Definitions; 2.2 Description of the Construction; 2.3 Bounding the Treewidth; 3 Proof of the Main Result; 3.1 Number of Constructible Triples (, F, N); 3.2 Bounding the Number of Duplicates; 3.3 Choosing the Parameter s; 4 Concluding Remarks and Further Research; References; Uniquely Restricted Matchings and Edge Colorings; 1 Introduction; 2 Approximation Algorithms for Bipartite Graphs; 3 Upper Bounds on ur'(G); 4 Concluding Remarks; References.
Defective Coloring on Classes of Perfect Graphs1 Introduction; 2 Preliminaries and Definitions; 3 NP-Hardness on Cographs; 4 Polynomial Time Algorithm on Trivially Perfect Graphs; 5 Algorithms on Cographs; 5.1 Algorithm for Small Deficiency; 5.2 Algorithm for Few Colors; 5.3 Sub-Exponential Time Algorithm; 6 Split and Chordal Graphs; 6.1 Hardness for Bounded Deficiency; 6.2 Hardness for Bounded Number of Colors; 6.3 A Dynamic Programming Algorithm; 7 Conclusions; References; Token Sliding on Chordal Graphs; 1 Introduction; 2 Hardness Results; 2.1 Split Graphs; 2.2 Bipartite Graphs.