000 05271nam a22005895i 4500
001 978-3-642-45043-3
003 DE-He213
005 20200421111208.0
007 cr nn 008mamaa
008 131112s2013 gw | s |||| 0|eng d
020 _a9783642450433
_9978-3-642-45043-3
024 7 _a10.1007/978-3-642-45043-3
_2doi
050 4 _aQA76.9.M35
072 7 _aPBD
_2bicssc
072 7 _aUYAM
_2bicssc
072 7 _aCOM018000
_2bisacsh
072 7 _aMAT008000
_2bisacsh
082 0 4 _a004.0151
_223
245 1 0 _aGraph-Theoretic Concepts in Computer Science
_h[electronic resource] :
_b39th International Workshop, WG 2013, L�ubeck, Germany, June 19-21, 2013, Revised Papers /
_cedited by Andreas Brandst�adt, Klaus Jansen, R�udiger Reischuk.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2013.
300 _aXX, 430 p. 114 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v8165
505 0 _aTree-Like Structures in Graphs: A Metric Point of View -- Overview of New Approaches for Approximating TSP -- Linear Rank-Width and Linear Clique-Width of Trees -- Threshold-Coloring and Unit-Cube Contact Representation of Graphs -- Rolling Upward Planarity Testing of Strongly Connected Graphs -- Towards a Provably Resilient Scheme for Graph-Based Watermarking -- The Normal Graph Conjecture for Classes of Sparse Graphs -- On the Parameterized Complexity of Computing Graph Bisections -- Fixed-Parameter Tractability and Characterizations of Small Special Treewidth -- The (Sk(B5-Graph is a Spanner -- Graphs of Edge-Intersecting Non-splitting Paths in a Tree: Towards Hole Representations (Extended Abstract) -- Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs -- Equilateral L-Contact Graphs -- Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees -- Linear Separation of Total Dominating Sets in Graphs -- Sparse Square Roots -- Completing Colored Graphs to Meet a Target Property -- Colouring of Graphs with Ramsey-Type Forbidden Subgraphs -- Lower and Upper Bounds for Long Induced Paths in 3-Connected Planar Graphs -- Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time -- Thickness and Colorability of Geometric Graphs -- The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n-Cube -- FPT Is Characterized by Useful Obstruction Sets -- Excluding Graphs as Immersions in Surface Embedded -- OBDD-Based Representation of Interval Graphs -- Tight Upper Bounds for Minimum Feedback Arc Sets of Regular -- A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem -- On Retracts, Absolute Retracts, and Folds in Cographs -- Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(log log n) Colors -- On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs -- Certifying 3-Edge-Connectivity -- Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs -- Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs -- Beyond Knights and Knaves -- Drawing Graphs with Few Arcs -- Connecting Terminals and 2-Disjoint Connected Subgraphs.
520 _aThis book constitutes the thoroughly refereed proceedings of the 39th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2013, held in L�ubeck, Germany, in June 2013. The 34 revised full papers presented were carefully reviewed and selected from 61 submissions. The book also includes two abstracts. The papers cover a wide range of topics in graph theory related to computer science, such as structural graph theory with algorithmic or complexity applications; design and analysis of sequential, parallel, randomized, parameterized and distributed graph and network algorithms; computational complexity of graph and network problems; computational geometry; graph grammars, graph rewriting systems and graph modeling; graph drawing and layouts; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications.
650 0 _aComputer science.
650 0 _aData structures (Computer science).
650 0 _aAlgorithms.
650 0 _aComputer science
_xMathematics.
650 0 _aGeometry.
650 1 4 _aComputer Science.
650 2 4 _aDiscrete Mathematics in Computer Science.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
650 2 4 _aData Structures.
650 2 4 _aGeometry.
650 2 4 _aAlgorithms.
700 1 _aBrandst�adt, Andreas.
_eeditor.
700 1 _aJansen, Klaus.
_eeditor.
700 1 _aReischuk, R�udiger.
_eeditor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783642450426
830 0 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v8165
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-642-45043-3
912 _aZDB-2-SCS
912 _aZDB-2-LNC
942 _cEBK
999 _c54250
_d54250