Graph-theoretic concepts in computer science : 43rd International Workshop, WG 2017, Eindhoven, the Netherlands, June 21-23, 2017, Revised selected papers /: 43rd International Workshop, WG 2017, Eindhoven, the Netherlands, June 21-23, 2017, Revised selected papers. (2017)

• Record Type: Book
• Other Titles: WG 2017
• Further Information: Note: Hans L. Bodlaender, Gerhard J. Woeginger (eds.).
• Editors: Bodlaender, H. L; Woeginger, Gerhard
• Other Names: International Workshop WG, 43rd
• Contents: 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[1]-Hard; 1 Introduction; 2 Preliminaries; 3 W[1]-HardNess of SumCSP; 4 W[1]-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.
• Publisher Details: Cham, Switzerland : Springer
• Publication Date: 2017
• Extent: 1 online resource (xiii, 440 pages), illustrations
• Subjects: 004.01/51; Computer science; Graph theory -- Data processing -- Congresses; Computer science -- Mathematics -- Congresses; Computational complexity; Computer software; Data structures (Computer science); Computer graphics; Geometry; Algorithms; Computer science -- Mathematics; Graph theory -- Data processing; 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; Discrete Mathematics in Computer Science; Algorithm Analysis and Problem Complexity; Data Structures; Computer Graphics; Geometry; Algorithms; Electronic books; Conference papers and proceedings
• Languages: English
• ISBNs: 9783319687056; 3319687050
• Related ISBNs: 9783319687049
• Notes: Note: Online resource; title from PDF title page (SpringerLink, viewed November 9, 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.