000 04912nam a22006135i 4500
001 978-3-030-30786-8
003 DE-He213
005 20240423125053.0
007 cr nn 008mamaa
008 190911s2019 sz | s |||| 0|eng d
020 _a9783030307868
_9978-3-030-30786-8
024 7 _a10.1007/978-3-030-30786-8
_2doi
050 4 _aQA71-90
072 7 _aPBKS
_2bicssc
072 7 _aMAT041000
_2bisacsh
072 7 _aPBKS
_2thema
082 0 4 _a518
_223
245 1 0 _aGraph-Theoretic Concepts in Computer Science
_h[electronic resource] :
_b45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers /
_cedited by Ignasi Sau, Dimitrios M. Thilikos.
250 _a1st ed. 2019.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2019.
300 _aXXI, 394 p. 304 illus., 41 illus. in color.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v11789
505 0 _aLogic and Random Graphs -- Unavoidability and universality of digraphs -- Parameterized algorithms for geometric graphs via decomposition theorems -- Subexponential algorithms for variants of homomorphism problem in string graphs -- The 4-Steiner Root Problem -- Hamiltonicity below Dirac’s condition -- Maximum Independent Sets in Subcubic Graphs: New Results -- Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs -- Local approximation of the Maximum Cut in regular graphs -- Fixed-parameter tractability of counting small minimum (S,T)-cuts -- Fast Breadth-First Search in Still Less Space -- A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion -- Flip distances between graph orientations -- Graph functionality -- On Happy Colorings, Cuts, and Structural Parameterizations -- Shortest Reconfiguration of Matchings -- Travelling on Graphs with Small Highway Dimension -- The Power of Cut-Based Parameters for Computing Edge Disjoint Paths -- Geometric Representations of Dichotomous Ordinal Data -- Linear MIM-width of Trees -- Approximating Minimum Dominating Set on String graphs -- Classified Rank-Maximal Matchings and Popular Matchings -- Algorithms and Hardness -- Maximum Matchings and Minimum Blocking Sets in Theta-6 Graphs -- A polynomial-time algorithm for the independent set problem in $\{P_{10},C_4,C_6\}$-free graphs -- Independent Set Reconfiguration Parameterized by Modular-Width -- Counting independent sets in graphs with bounded bipartite pathwidth -- Intersection Graphs of Non-Crossing Paths -- Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs -- Color Refinement, Homomorphisms, and Hypergraphs -- 3-colorable planar graphs have an intersection segment representation using 3 slopes -- The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms -- Minimal separators in graph classes defined by small forbidden induced subgraphs.
520 _aThis 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.
650 0 _aMathematics
_xData processing.
650 0 _aComputer science
_xMathematics.
650 0 _aDiscrete mathematics.
650 0 _aArtificial intelligence
_xData processing.
650 0 _aAlgorithms.
650 0 _aComputer arithmetic and logic units.
650 1 4 _aComputational Mathematics and Numerical Analysis.
650 2 4 _aDiscrete Mathematics in Computer Science.
650 2 4 _aData Science.
650 2 4 _aAlgorithms.
650 2 4 _aArithmetic and Logic Structures.
700 1 _aSau, Ignasi.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aThilikos, Dimitrios M.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783030307851
776 0 8 _iPrinted edition:
_z9783030307875
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v11789
856 4 0 _uhttps://doi.org/10.1007/978-3-030-30786-8
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cSPRINGER
999 _c173891
_d173891