Graph-Theoretic Concepts in Computer Science : 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers / edited by Ignasi Sau, Dimitrios M. Thilikos.

Format:

Book

Contributor:

Sau, Ignasi, editor.

Thilikos, Dimitrios M., editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 11789.

Theoretical Computer Science and General Issues ; 11789

Language:

English

Subjects (All):

Computer science--Mathematics.

Computer science.

Data structures (Computer science).

Algorithms.

Computer arithmetic and logic units.

Computational Mathematics and Numerical Analysis.

Discrete Mathematics in Computer Science.

Data Structures.

Algorithm Analysis and Problem Complexity.

Arithmetic and Logic Structures.

Local Subjects:

Computational Mathematics and Numerical Analysis.

Discrete Mathematics in Computer Science.

Data Structures.

Algorithm Analysis and Problem Complexity.

Arithmetic and Logic Structures.

Physical Description:

1 online resource (XXI, 394 pages) : 304 illustrations, 41 illustrations in color.

Edition:

First edition 2019.

Contained In:

Springer eBooks

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2019.

System Details:

text file PDF

Summary:

This book constitutes the revised papers of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019, held in Vall de Núria, Spain, in June 2019. The 29 full papers presented in this volume were carefully reviewed and selected from 87 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.

Contents:

Logic and Random Graphs

Unavoidability and universality of digraphs

Parameterized algorithms for geometric graphs via decomposition theorems

Subexponential algorithms for variants of homomorphism problem in string graphs

The 4-Steiner Root Problem

Hamiltonicity below Dirac's condition

Maximum Independent Sets in Subcubic Graphs: New Results

Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs

Local approximation of the Maximum Cut in regular graphs

Fixed-parameter tractability of counting small minimum (S,T)-cuts

Fast Breadth-First Search in Still Less Space

A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion

Flip distances between graph orientations

Graph functionality

On Happy Colorings, Cuts, and Structural Parameterizations

Shortest Reconfiguration of Matchings

Travelling on Graphs with Small Highway Dimension

The Power of Cut-Based Parameters for Computing Edge Disjoint Paths

Geometric Representations of Dichotomous Ordinal Data

Linear MIM-width of Trees

Approximating Minimum Dominating Set on String graphs

Classified Rank-Maximal Matchings and Popular Matchings

Algorithms and Hardness

Maximum Matchings and Minimum Blocking Sets in Theta-6 Graphs

A polynomial-time algorithm for the independent set problem in $\{P_ ,C_4,C_6\}$-free graphs

Independent Set Reconfiguration Parameterized by Modular-Width

Counting independent sets in graphs with bounded bipartite pathwidth

Intersection Graphs of Non-Crossing Paths

Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs

Color Refinement, Homomorphisms, and Hypergraphs

3-colorable planar graphs have an intersection segment representation using 3 slopes

The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms

Minimal separators in graph classes defined by small forbidden induced subgraphs.

Other Format:

Printed edition:

ISBN:

978-3-030-30786-8

9783030307868

Access Restriction:

Restricted for use by site license.