Treewidth: Characterizations, Applications, and Computations
From MaRDI portal
Publication:3522937
DOI10.1007/11917496_1zbMath1167.68404OpenAlexW1504895562MaRDI QIDQ3522937
Publication date: 4 September 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11917496_1
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ The label cut problem with respect to path length and label frequency ⋮ Semiring induced valuation algebras: exact and approximate local computation algorithms ⋮ Parameterized orientable deletion ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Are there any good digraph width measures? ⋮ Directed elimination games ⋮ Characterization and Recognition of Digraphs of Bounded Kelly-width ⋮ The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs ⋮ Constant-degree graph expansions that preserve treewidth ⋮ A short note on the complexity of computing strong pathbreadth ⋮ Revisiting Decomposition by Clique Separators ⋮ Unnamed Item ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ A note on the complexity of matching patterns with variables ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ On the complexity of computing treebreadth ⋮ Compact Navigation and Distance Oracles for Graphs with Small Treewidth ⋮ Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ The critical node detection problem in networks: a survey ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ Recognizing digraphs of Kelly-width 2 ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Are There Any Good Digraph Width Measures? ⋮ Most frugal explanations in Bayesian networks ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ A Local Search Algorithm for Branchwidth ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines ⋮ On the (di)graphs with (directed) proper connection number two ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ On the Complexity of Computing Treebreadth ⋮ Structurally parameterized \(d\)-scattered set ⋮ The parameterized complexity of the induced matching problem ⋮ Unnamed Item ⋮ The Valve Location Problem in Simple Network Topologies ⋮ Efficient parallel algorithms for parameterized problems ⋮ Estimating the probability of meeting a deadline in schedules and plans ⋮ Tree-length equals branch-length ⋮ Tree decompositions and social graphs ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ On the tree-depth and tree-width in heterogeneous random graphs
