LEADER 06365nam 22008055 450 001 996466068603316 005 20230221160430.0 010 $a3-540-74839-3 024 7 $a10.1007/978-3-540-74839-7 035 $a(CKB)1000000000490619 035 $a(SSID)ssj0000317988 035 $a(PQKBManifestationID)11211930 035 $a(PQKBTitleCode)TC0000317988 035 $a(PQKBWorkID)10307855 035 $a(PQKB)10707962 035 $a(DE-He213)978-3-540-74839-7 035 $a(MiAaPQ)EBC3068137 035 $a(PPN)123731593 035 $a(EXLCZ)991000000000490619 100 $a20100301d2007 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aGraph-Theoretic Concepts in Computer Science$b[electronic resource] $e33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers /$fedited by Andreas Brandstädt, Dieter Kratsch, Haiko Müller 205 $a1st ed. 2007. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2007. 215 $a1 online resource (XIII, 344 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4769 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-74838-5 320 $aIncludes bibliographical references and index. 327 $aComputational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs -- Recognizing Bipartite Tolerance Graphs in Linear Time -- Graph Searching in a Crime Wave -- Monotonicity of Non-deterministic Graph Searching -- Tree-Width and Optimization in Bounded Degree Graphs -- On Restrictions of Balanced 2-Interval Graphs -- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions -- The Clique-Width of Tree-Power and Leaf-Power Graphs -- NLC-2 Graph Recognition and Isomorphism -- A Characterisation of the Minimal Triangulations of Permutation Graphs -- The 3-Steiner Root Problem -- On Finding Graph Clusterings with Maximum Modularity -- On Minimum Area Planar Upward Drawings of Directed Trees and Other Families of Directed Acyclic Graphs -- A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs -- Approximation Algorithms for Geometric Intersection Graphs -- An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem -- Mixing 3-Colourings in Bipartite Graphs -- Minimum-Weight Cycle Covers and Their Approximability -- On the Number of ?-Orientations -- Complexity and Approximation Results for the Connected Vertex Cover Problem -- Segmenting Strings Homogeneously Via Trees -- Characterisations and Linear-Time Recognition of Probe Cographs -- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete -- Proper Helly Circular-Arc Graphs -- Pathwidth of Circular-Arc Graphs -- Characterization and Recognition of Digraphs of Bounded Kelly-width -- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms -- Obtaining a Planar Graph by Vertex Deletion -- Mixed Search Number and Linear-Width of Interval and Split Graphs -- Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation -- The Complexity of Bottleneck Labeled Graph Problems. 330 $aThe 33rd International Conference ?Workshop on Graph-Theoretic Concepts in Computer Science? (WG 2007) took place in the Conference Center in old castleinDornburgnearJena,Germany,June21?23,2007.Theapproximately80 participants came from various countries all over the world, among them Brazil, Canada, the Czech Republic, France, UK, Greece, Hungary, Italy, Japan, The Netherlands, Norway, Sweden, Taiwan, and the USA. WG 2007 continued the series of 32 previous WG conferences. Since 1975, the WG conference has taken place 20 times in Germany, four times in The Netherlands, twice in Austria as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France and in Norway. The WG conference traditionally aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent researchresults and to identify and exploredirections of future research. Thecontinuinginterestinthe WGconferenceswasre?ectedin thehighn- ber of submissions; 99 papers were submitted and in an evaluation process with four reports per submission, 30 papers were accepted by the Program Comm- tee for the conference. Due to the high number of submissions and the limited schedule of 3 days, various good papers could not be accepted. There were invited talks by Ming-Yang Kao (Evanston, Illinois) on algori- mic DNA assembly, and by Klaus Jansen (Kiel, Germany) on approximation algorithms for geometric intersection graphs. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4769 606 $aComputer science 606 $aComputer simulation 606 $aAlgorithms 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aArtificial intelligence?Data processing 606 $aTheory of Computation 606 $aComputer Modelling 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 606 $aData Science 615 0$aComputer science. 615 0$aComputer simulation. 615 0$aAlgorithms. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 0$aArtificial intelligence?Data processing. 615 14$aTheory of Computation. 615 24$aComputer Modelling. 615 24$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 615 24$aData Science. 676 $a004.0151 702 $aBrandstädt$b Andreas$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aKratsch$b Dieter$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aMüller$b Haiko$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996466068603316 996 $aGraph-Theoretic Concepts in Computer Science$92569248 997 $aUNISA