Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. Martin Charles Golumbic

    1. Department of Computer Science, Caesarea Rothschild Institute (CRI), Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Michal Stern

    1. The Academic College of Tel Aviv, Unit of Statistics and Probability Studies, Yaffo, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Avivit Levy

    1. Shenkar College and Caesarea Rothschild Institute (CRI), University of Haifa, Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Gila Morgenstern

    1. Caesarea Rothschild Institute (CRI), Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Fast conference proceedings
  • State-of-the-art report
  • Up to date results

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

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

Included in the following conference series:

Conference proceedings info: WG 2012.

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 39.99
Price excludes VAT (USA)
  • Available as 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

Licence this eBook for your library

Institutional subscriptions

Table of contents (33 papers)

  1. Front Matter

    Download chapter PDF

  3. Poster Session

    1. Student Poster Session

      • Martin Charles Golumbic, Michal Stern, Avivit Levy, Gila Morgenstern
      Pages 4-6

  4. Papers

    1. Triangulation and Clique Separator Decomposition of Claw-Free Graphs

      • Anne Berry, Annegret Wagler
      Pages 7-21

    2. Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs

      • Flavia Bonomo, Gianpaolo Oriolo, Claudia Snels
      Pages 22-33

    3. Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs

      • Stefan Kratsch, Pascal Schweitzer
      Pages 34-45

    4. Optimization Problems in Dotted Interval Graphs

      • Danny Hermelin, Julián Mestre, Dror Rawitz
      Pages 46-56

    5. The Maximum Clique Problem in Multiple Interval Graphs (Extended Abstract)

      • Mathew C. Francis, Daniel Gonçalves, Pascal Ochem
      Pages 57-68

    6. Solutions for the Stable Roommates Problem with Payments

      • Péter Biró, Matthijs Bomhoff, Petr A. Golovach, Walter Kern, Daniël Paulusma
      Pages 69-80

    7. Which Multi-peg Tower of Hanoi Problems Are Exponential?

      • Daniel Berend, Amir Sapir
      Pages 81-90

    8. h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area

      • Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani
      Pages 91-102

    9. The Duals of Upward Planar Graphs on Cylinders

      • Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer
      Pages 103-113

    10. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases

      • Leah Epstein, Asaf Levin, Gerhard J. Woeginger
      Pages 114-125

    11. Determining the L(2,1)-Span in Polynomial Space

      • Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Paweł Rzążewski
      Pages 126-137

    12. On the Minimum Degree Up to Local Complementation: Bounds and Complexity

      • Jérôme Javelle, Mehdi Mhalla, Simon Perdrix
      Pages 138-147

    13. On the Stable Degree of Graphs

      • Haiko Müller
      Pages 148-159

    14. A 9k Kernel for Nonseparating Independent Set in Planar Graphs

      • Łukasz Kowalik, Marcin Mucha
      Pages 160-171

    15. Parameterized Algorithms for Even Cycle Transversal

      • Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
      Pages 172-183
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

This book constitutes the thoroughly refereed proceedings of the 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012) held in Jerusalem, Israel on June 26-28, 2012. The 29 revised full papers presented were carefully selected and reviewed from 78 submissions. The papers are solicited describing original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, randomized, parameterized, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, random graphs, diagram methods, and support of these concepts by suitable implementations. The scope of WG includes all applications of graph-theoretic concepts in Computer Science, including data structures, data bases, programming languages, computational geometry, tools for software construction, communications, computing on the web, models of the web and scale-free networks, mobile computing, concurrency, computer architectures, VLSI, artificial intelligence, graphics, CAD, operations research, and pattern recognition

Editors and Affiliations

  • Department of Computer Science, Caesarea Rothschild Institute (CRI), Haifa, Israel

    Martin Charles Golumbic

  • The Academic College of Tel Aviv, Unit of Statistics and Probability Studies, Yaffo, Israel

    Michal Stern

  • Shenkar College and Caesarea Rothschild Institute (CRI), University of Haifa, Haifa, Israel

    Avivit Levy

  • Caesarea Rothschild Institute (CRI), Haifa, Israel

    Gila Morgenstern

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation