Graph-theoretic concepts in computer science : 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers /: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers. (2019)

• Record Type: Book
• Other Titles: WG 2019
• Further Information: Note: Ignasi Sau, Dimitrios M. Thilikos (eds.).
• Editors: Sau, Ignasi; Thilikos, Dimitrios M
• Other Names: International Workshop WG, 45th
• Contents: Logic 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.
• Publisher Details: Cham, Switzerland : Springer
• Publication Date: 2019
• Extent: 1 online resource (xxi, 394 pages), illustrations (some color)
• Subjects: 004.01/51; Graph theory -- Data processing -- Congresses; Computer science -- Mathematics -- Congresses; Electronic books
• Languages: English
• ISBNs: 9783030307868; 3030307867
• Related ISBNs: 9783030307851
• Notes: Note: Online resource; title from PDF title page (SpringerLink, viewed September 25, 2019).
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.