Graph theoretic concepts in computer science

Viac o knihe

The content includes invited lectures and regular papers focusing on various aspects of graph theory and algorithms. Topics cover hypertree decompositions, combinatorial search in bioinformatics, and domination search in graphs with low dominating-target-number. Key discussions include dynamic algorithms for recognizing permutation graphs, approximating rank-width and clique-width, and computing the Tutte polynomial for graphs of bounded clique-width. The complexity of minimizing NLC-width is highlighted, along with channel assignment and improper choosability of graphs. Other significant areas include treewidth computation, optimal broadcast domination, and algorithms for matrix comparability in partial orders. The collection also addresses network discovery, stable cutsets in claw-free and planar graphs, and induced subgraphs with bounded degree and treewidth. It features optimal hypergraph tree-realization, fixed-parameter algorithms for protein similarity, and randomized broadcasting in star graphs. Approximation algorithms for various problems, including the bi-criteria weighted max-cut and weighted independent set problems, are also discussed. The work emphasizes efficient triangulations and blocks for computing branchwidth, and it explores the tractability of closest leaf powers and spectral partitioning errors. Additionally, it presents linear-time counting algorithms for independent sets in chordal graphs and faster d