| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNINA9910427706603321 |
|
|
Titolo |
Graph-Theoretic Concepts in Computer Science : 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers / / edited by Isolde Adler, Haiko Müller |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 2020.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (XV, 416 p. 50 illus.) |
|
|
|
|
|
|
Collana |
|
Theoretical Computer Science and General Issues, , 2512-2029 ; ; 12301 |
|
|
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computer science - Mathematics |
Discrete mathematics |
Algorithms |
Artificial intelligence - Data processing |
Mathematics - Data processing |
Discrete Mathematics in Computer Science |
Data Science |
Symbolic and Algebraic Manipulation |
Computational Mathematics and Numerical Analysis |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
|
|
|
|
|
Nota di contenuto |
|
Combinatorial Bounds for Conflict-free Coloring on Open Neighborhoods -- Guarding Quadrangulations and Stacked Triangulations with Edges -- Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space -- Parameterized Inapproximability of Independent Set in H-Free Graphs -- Clique-Width of Point Configurations -- On the complexity of finding large odd induced subgraphs and odd colorings -- Knot Diagrams of Treewidth Two -- Treewidth versus clique number in graph classes with a forbidden structure -- Graph Isomorphism Restricted by Lists -- Clique-Width: Harnessing the Power of Atoms -- Edge elimination and weighted graph classes -- Well-partitioned chordal graphs: obstruction set and disjoint paths -- Plattenbauten: |
|
|
|
|
|
|
|
|
|
|
|
Touching Rectangles in Space Universal Geometric Graphs -- Computing Subset Transversals in H-Free Graphs -- Feedback Edge Sets in Temporal Graphs -- On flips in planar matchings -- Degree Distribution for Duplication-Divergence Graphs: Large Deviations -- On Finding Balanced Bicliques via Matchings -- Finding large matchings in 1-planar graphs of minimum degree 3 -- Strong cliques in diamond-free graphs -- Recognizing k-Clique Extendible Orderings -- Linear-Time Recognition of Double-Threshold Graphs -- Characterization and Linear-time Recognition of Paired Threshold Graphs -- Drawing Graphs as Spanners -- Inserting one edge into a simple drawing is hard -- Bitonic st-orderings for Upward Planar Graphs: The Variable Embedding Setting -- 2.5-Connectivity: Unique Components, Critical Graphs, and Applications Stable Structure on Safe Set Problems in Vertex-weighted Graphs II – Recognition and Complexity -- The linear arboricity conjecture for 3-degenerate graphs -- Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width -- Weighted Additive Spanners. |
|
|
|
|
|
|
Sommario/riassunto |
|
This book constitutes the revised papers of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020, held in Leeds, UK, in June 2020. The workshop was held virtually due to the COVID-19 pandemic. The 32 full papers presented in this volume were carefully reviewed and selected from 94 submissions. They cover a wide range of areas, aiming to present emerging research results and to identify and explore directions of future research of concepts on graph theory and how they can be applied to various areas in computer science. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2. |
Record Nr. |
UNINA9910768437903321 |
|
|
Titolo |
Graph-Theoretic Concepts in Computer Science : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers / / edited by Hans L. Bodlaender |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 2003.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (XII, 392 p.) |
|
|
|
|
|
|
Collana |
|
Lecture Notes in Computer Science, , 0302-9743 ; ; 2880 |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computers |
Computer simulation |
Algorithms |
Data structures (Computer science) |
Numerical analysis |
Computer science—Mathematics |
Theory of Computation |
Simulation and Modeling |
Algorithm Analysis and Problem Complexity |
Data Structures |
Numeric Computing |
Discrete Mathematics in Computer Science |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Bibliographic Level Mode of Issuance: Monograph |
|
|
|
|
|
|
Nota di bibliografia |
|
Includes bibliographical references and index. |
|
|
|
|
|
|
Nota di contenuto |
|
Invited Lecture -- Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT -- Matching, Edge-Colouring, and Dimers -- Regular Papers -- Minimum Flow Time Graph Ordering -- Searching Is Not Jumping -- Incremental Integration Tools for Chemical Engineering: An Industrial Application of Triple Graph Grammars -- The Minimum Degree Heuristic and the Minimal Triangulation Process -- Generalized Parametric Multi-terminal Flows Problem -- Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generation -- The Complexity of the Matching-Cut Problem for Planar |
|
|
|
|
|
|
|
|
|
|
|
Graphs and Other Graph Classes -- Tree Spanners for Bipartite Graphs and Probe Interval Graphs -- A Simple Linear Time LexBFS Cograph Recognition Algorithm -- Backbone Colorings for Networks -- Greedy Edge-Disjoint Paths in Complete Graphs -- Graph-Based Approaches to Software Watermarking -- Completely Connected Clustered Graphs -- An FPT Algorithm for Set Splitting -- Drawing Planar Graphs on a Curve -- Tree-Partitions of k-Trees with Applications in Graph Layout -- Resource Allocation Problems in Multifiber WDM Tree Networks -- An Improved Upper Bound on the Crossing Number of the Hypercube -- NCE Graph Grammars and Clique-Width -- Chordal Probe Graphs -- Subgraph Induced Planar Connectivity Augmentation -- On the Recognition of General Partition Graphs -- Short Cycles in Planar Graphs -- Complexity of Hypergraph Coloring and Seidel’s Switching -- Feedback Vertex Set and Longest Induced Path on AT-Free Graphs -- The Complexity of Graph Contractions -- Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs -- The Probabilistic Minimum Coloring Problem -- Recognizing Bipolarizable and P 4-Simplicial Graphs -- Coloring Powers of Graphs of Bounded Clique-Width -- Erratum -- Erratum: Cycles in Generalized Networks. |
|
|
|
|
|
|
Sommario/riassunto |
|
The 29th International Workshop on Graph-Theoretic Concepts in Computer Science(WG2003)washeldintheMennorodeconferenceCenterinElspeet,The Netherlands.TheworkshopwasorganizedbytheCenterforAlgorithmicSystems of the Institute of Information and Computing Sciences of Utrecht University. The workshop took place June 19–21, 2003. The 72 participants of WG 2003 came from universities and research institutes from 18 di?erent countries and ?ve di?erent continents. The workshop looks back at a long tradition. It was ?rst held in 1975, and has been held 20 times in Germany, twice in Austria, and once in Italy, Slo- kia, Switzerland, and the Czech Republic, and has now been held for the third time in The Netherlands. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computerscience,orbyextractingnewproblemsfromapplications.Itisdevoted to the theoretical and practical aspects of graph concepts in computer science. The goal is to present recent research results and to identify and explore - rections of future research. The talks given at the workshop showed how recent research results from algorithmic graph theory can be used in computer science and which graph-theoretic questions arise from new developments in computer science. |
|
|
|
|
|
|
|
| |