Skip to main content
  • Conference proceedings
  • © 2016

Graph-Theoretic Concepts in Computer Science

42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers

Editors:

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

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

Conference series link(s): WG: International Workshop on Graph-Theoretic Concepts in Computer Science

Conference proceedings info: WG 2016.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.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

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

Table of contents (26 papers)

  1. Front Matter

    Pages I-X
  2. Sequences of Radius k for Complete Bipartite Graphs

    • Michał Dębski, Zbigniew Lonc, Paweł Rzążewski
    Pages 1-12
  3. Approximate Association via Dissociation

    • Jie You, Jianxin Wang, Yixin Cao
    Pages 13-24
  4. Geodetic Convexity Parameters for Graphs with Few Short Induced Paths

    • Mitre C. Dourado, Lucia D. Penso, Dieter Rautenbach
    Pages 25-37
  5. Weighted Efficient Domination for \(P_6\)-Free and for \(P_5\)-Free Graphs

    • Andreas Brandstädt, Raffaele Mosca
    Pages 38-49
  6. Finding Two Edge-Disjoint Paths with Length Constraints

    • Leizhen Cai, Junjie Ye
    Pages 62-73
  7. Packing and Covering Immersion Models of Planar Subcubic Graphs

    • Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos
    Pages 74-84
  8. The Maximum Weight Stable Set Problem in (\(P_6\), bull)-Free Graphs

    • Frédéric Maffray, Lucas Pastor
    Pages 85-96
  9. Parameterized Power Vertex Cover

    • Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis
    Pages 97-108
  10. Exhaustive Generation of k-Critical \({\mathcal H}\)-Free Graphs

    • Jan Goedgebeur, Oliver Schaudt
    Pages 109-120
  11. Induced Separation Dimension

    • Emile Ziedan, Deepak Rajendraprasad, Rogers Mathew, Martin Charles Golumbic, Jérémie Dusart
    Pages 121-132
  12. Tight Bounds for Gomory-Hu-like Cut Counting

    • Rajesh Chitnis, Lior Kamma, Robert Krauthgamer
    Pages 133-144
  13. Eccentricity Approximating Trees

    • Feodor F. Dragan, Ekkehard Köhler, Hend Alrasheed
    Pages 145-157
  14. Vertex Cover Structural Parameterization Revisited

    • Fedor V. Fomin, Torstein J. F. Strømme
    Pages 171-182
  15. Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability

    • Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordechai Shalom
    Pages 195-206
  16. On Edge Intersection Graphs of Paths with 2 Bends

    • Martin Pergel, Paweł Rzążewski
    Pages 207-219

Other Volumes

  1. Graph-Theoretic Concepts in Computer Science

About this book

This book constitutes revised selected papers from the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016, held in Istanbul, Turkey, in June 2016.
The 25 papers presented in this volume were carefully reviewed and selected from 74 submissions.The WG conferences aim to connect theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas of computer science and by extracting new graph problems from applications. Their goal is to present new research results and to identify and explore directions of future research. 

Editors and Affiliations

  • University of Bergen, Bergen, Norway

    Pinar Heggernes

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.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