Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers

  • Conference proceedings
  • © 2019

Overview

Editors:
  1. Ignasi Sau

    1. CNRS, LIRMM, Université de Montpellier, Montpellier, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Dimitrios M. Thilikos

    1. CNRS, LIRMM, Université de Montpellier, Montpellier, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 11789)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: WG 2019.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 74.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (29 papers)

  1. Front Matter

    Pages i-xxi
    Download chapter PDF

  2. Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs

    • Karolina Okrasa, Paweł Rzążewski
    Pages 1-13

  3. The 4-Steiner Root Problem

    • Guillaume Ducoffe
    Pages 14-26

  4. Hamiltonicity Below Dirac’s Condition

    • Bart M. P. Jansen, László Kozma, Jesper Nederlof
    Pages 27-39

  5. Maximum Independent Sets in Subcubic Graphs: New Results

    • Ararat Harutyunyan, Michael Lampis, Vadim Lozin, Jérôme Monnot
    Pages 40-52

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

    • Meike Hatzel, Roman Rabinovich, Sebastian Wiederrecht
    Pages 53-65

  7. Local Approximation of the Maximum Cut in Regular Graphs

    • Étienne Bamas, Louis Esperet
    Pages 66-78

  8. Fixed-Parameter Tractability of Counting Small Minimum (S, T)-Cuts

    • Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel, Joanna Tomasik
    Pages 79-92

  9. Fast Breadth-First Search in Still Less Space

    • Torben Hagerup
    Pages 93-105

  10. A Turing Kernelization Dichotomy for Structural Parameterizations of \(\mathcal {F}\)-Minor-Free Deletion

    • Huib Donkers, Bart M. P. Jansen
    Pages 106-119

  11. Flip Distances Between Graph Orientations

    • Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner et al.
    Pages 120-134

  12. Graph Functionality

    • Bogdan Alecu, Aistis Atminas, Vadim Lozin
    Pages 135-147

  13. On Happy Colorings, Cuts, and Structural Parameterizations

    • Ivan Bliznets, Danil Sagunov
    Pages 148-161

  14. Shortest Reconfiguration of Matchings

    • Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler
    Pages 162-174

  15. Travelling on Graphs with Small Highway Dimension

    • Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann
    Pages 175-189

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

    • Robert Ganian, Sebastian Ordyniak
    Pages 190-204

  17. Geometric Representations of Dichotomous Ordinal Data

    • Patrizio Angelini, Michael A. Bekos, Martin Gronemann, Antonios Symvonis
    Pages 205-217

  18. Linear MIM-Width of Trees

    • Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset
    Pages 218-231

  19. Approximating Minimum Dominating Set on String Graphs

    • Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee
    Pages 232-243

  20. Classified Rank-Maximal Matchings and Popular Matchings – Algorithms and Hardness

    • Meghana Nasre, Prajakta Nimbhorkar, Nada Pulath
    Pages 244-257
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

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.

Editors and Affiliations

  • CNRS, LIRMM, Université de Montpellier, Montpellier, France

    Ignasi Sau, Dimitrios M. Thilikos

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation