Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger

• Pubblicazione: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017
• Edizione: 1st ed. 2017.
• Descrizione fisica: 1 online resource (XIII, 440 p. 87 illus.)
• Disciplina: 511.5
• Soggetto topico: Computer science—Mathematics; Discrete mathematics; Algorithms; Artificial intelligence—Data processing; Computer graphics; Geometry; Discrete Mathematics in Computer Science; Data Science; Computer Graphics
• Persona (resp. second.): BodlaenderHans L; WoegingerGerhard J
• Nota di contenuto: 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 Preliminaries -- 3 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 Graphs -- 1 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 Treewidth -- 1 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 Graphs -- 1 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 -- 3 Interval Graphs -- 3.1 Basic Facts on Independent Sets in Interval Graphs -- 3.2 Reachability -- 3.3 Connectivity -- References -- Computing Maximum Cliques in B2-EPG Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Typed Intervals and Projection Graphs -- 3.1 Typed Intervals -- 3.2 Projection Graphs -- 4 Maximum Clique in B2-EPG Graphs -- 4.1 Graphs with Z-Vertices -- 4.2 General B2-EPG Graphs -- 5 Colorings and -boundedness -- References -- Intersection Graphs of Rays and Grounded Segments -- 1 Introduction -- 2 Preliminaries -- 3 Cycle Lemma -- 4 Stretchability -- 5 Rays and Segments -- References -- On H-Topological Intersection Graphs. ; 1 Introduction -- 2 Recognition of T-Graphs -- 3 Recognition Hardness -- 4 Dominating Set -- References -- The Hardness of Embedding Grids and Walls -- 1 Introduction -- 2 Preliminaries -- 2.1 From Homomorphism to Colored Embedding -- 3 Frames and Skeletons -- 4 Conclusions -- References -- Approximately Coloring Graphs Without Long Induced Paths -- 1 Introduction -- 2 Algorithm -- 3 Hardness Result -- 4 Conclusion -- References -- New and Simple Algorithms for Stable Flow Problems -- 1 Introduction -- 2 Preliminaries -- 3 A Polynomial-Time Augmenting Path Algorithm for Stable Flows -- 4 Stable Flows with Restricted Intervals -- 4.1 Forced Edges -- 4.2 Forbidden Edges -- 5 Stable Multicommodity Flows -- 5.1 Problem Simplification -- 5.2 Integral Multicommodity Stable Flows -- References -- Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Partitioning 3-Partite Graphs -- 4 Applications of Our Technique -- References -- Finding Cut-Vertices in the Square Roots of a Graph -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Squares and Powers of Graphs -- 2.2 Graph Decompositions -- 3 Basic Properties of the Atoms in a Square -- 4 Computation of the Cut-Vertices from the Square -- 4.1 Recognition of the Essential Cut-Vertices -- 4.2 Sufficient Conditions for Non Essential Cut-Vertices -- 5 Reconstructing the Block-Cut Tree of a Square Root -- 6 Application to Trees of Cycle-Powers -- 7 Conclusion -- References -- The Minimum Shared Edges Problem on Grid-Like Graphs -- 1 Introduction -- 2 Preliminaries -- 3 On Bounded and Holey Grids -- 3.1 Bounded Grids -- 3.2 Holey Grids -- 3.3 Manhattan-Like Acyclic Digraphs -- 4 The Nonexistence of Polynomial Kernels -- 5 Conclusion -- References -- Linearly -Bounding (P6,C4)-Free Graphs -- 1 Introduction. ; 2 Preliminaries -- 3 The Structure of (P6,C4)-Free Atoms -- 4 -Bounding (P6,C4)-Free Graphs -- 5 A 3/2-Approximation Algorithm -- References -- Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2 -- 1 Introduction -- 2 Preliminaries -- 3 Outerplanar Roots -- 3.1 Structural Lemmas -- 3.2 The Algorithm -- 4 Roots of Pathwidth at Most Two -- 5 Conclusions -- References -- Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Enumeration of Maximal Irredundant Sets for Chordal Graphs -- 4 Enumeration of Maximal Irredundant Sets for Interval Graphs -- 5 Conclusions -- References -- The Minimum Conflict-Free Row Split Problem Revisited -- 1 Introduction -- 2 Formulations in Terms of Branchings in Directed Acyclic Graphs -- 3 A Strengthening of Dilworth's Theorem and Its Connection to the MCRS Problem -- 3.1 A Min-Max Relation Strengthening Dilworth's Theorem -- 3.2 Connection with the MCRS Problem -- 4 (In)approximability Issues -- 4.1 Hardness Results -- 4.2 2-Approximating and via Laminar Set Families -- 4.3 Two Approximation Algorithms for Computing and -- 5 Conclusion -- References -- Drawing Planar Graphs with Few Geometric Primitives -- 1 Introduction -- 2 Trees with Segments on the Grid -- 3 Planar 3-Trees with Few Segments on the Grid -- 4 Maximal Outerplanar Graphs with Segments on the Grid -- 5 Triangulations and Planar Graphs with Circular Arcs -- References -- Mixed Dominating Set: A Parameterized Perspective -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for MDS Parameterized by the Solution Size -- 4 Outline of Algorithm for MDS Parameterized by Treewidth -- 5 Lower Bounds -- 6 Conclusion -- References -- Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity -- 1 Introduction -- 1.1 Related Work. ; 1.2 Our Contribution -- 2 Preliminaries -- 2.1 MSO and Its Extensions -- 2.2 Treewidth and Neighborhood Diversity -- 3 Graphs of Bounded Neighborhood Diversity -- 4 XP Algorithm for MSOGL on Bounded Treewidth -- 4.1 CSP, MSO and Treewidth -- 4.2 CSP Instance Construction -- 5 Conclusions -- References -- Extending Partial Representations of Trapezoid Graphs -- 1 Introduction -- 2 Modular Decomposition and Transitive Orientations -- 3 Trapezoid Models -- 4 Extending Partial Representations of Trapezoid Posets -- 5 Extending Partial Representations of Trapezoid Graphs -- References -- On Low Rank-Width Colorings -- 1 Introduction and Main Results -- 2 Preliminaries -- 3 Powers of Sparse Graphs -- 4 Other Positive Results -- 5 Negative Results -- 6 Erdős-Hajnal property and -boundedness -- 7 Conclusions -- References -- On Strongly Chordal Graphs That Are Not Leaf Powers -- 1 Introduction -- 2 Preliminary Notions -- 3 Alternating Cycles and Quartets in Leaf Powers -- 4 Strongly Chordal Graphs That Are Not Leaf Powers -- 5 Hardness of Finding rq in Chordal Graphs -- 6 Conclusion -- References -- New Results on Weighted Independent Domination -- 1 Introduction -- 2 Preliminaries -- 2.1 Modular Decomposition -- 2.2 Antineighborhood Decomposition -- 3 WID in (P5,P5)-Free Graphs -- 3.1 Decomposition Scheme -- 3.2 Application to (P5,P5)-Free Graphs -- 4 WID in (P5, P3+P2)-Free Graphs -- 5 Concluding Remarks and Open Problems -- References -- The Parameterized Complexity of the Equidomination Problem -- 1 Introduction -- 2 Twin Relation -- 3 Properties of Twin Classes Regarding Equidomination -- 4 An XP Algorithm for the k-EQUIDOMINATION Problem -- 5 Reduction Rules -- 6 Main Results -- 7 Hereditarily Equidominating Graphs -- 8 Conclusion and Outlook -- References -- Homothetic Triangle Contact Representations -- 1 Introduction -- 2 Schnyder Woods. ; 3 The System of Linear Equations.
• Sommario/riassunto: 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. .
• Titolo autorizzato: Graph-Theoretic Concepts in Computer Science
• ISBN: 3-319-68705-0
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910484501203321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 10520