Finding Branch-Decompositions and Rank-Decompositions
From MaRDI portal
Publication:5902074
DOI10.1137/070685920zbMath1163.05331OpenAlexW2140285470MaRDI QIDQ5902074
Publication date: 22 June 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070685920
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (56)
Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ Containment of Monadic Datalog Programs via Bounded Clique-Width ⋮ Solving Problems on Graphs of High Rank-Width ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ The rank-width of edge-coloured graphs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ A Simpler Self-reduction Algorithm for Matroid Path-Width ⋮ Rank-width: algorithmic and structural results ⋮ Finding branch-decompositions of matroids, hypergraphs, and more ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Subgraph complementation ⋮ Meta-kernelization using well-structured modulators ⋮ Tangle bases: Revisited ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Meta-kernelization with structural parameters ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ Decomposition width of matroids ⋮ Compact labelings for efficient first-order model-checking ⋮ Automata for the verification of monadic second-order graph properties ⋮ Parameterized Complexity of Safe Set ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Solving problems on graphs of high rank-width ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ Digraph width measures in parameterized algorithmics ⋮ Unnamed Item ⋮ Latency-bounded target set selection in social networks ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Branch-depth: generalizing tree-depth of graphs ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ Parameterized algorithms for the happy set problem ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ The rank-width of the square grid ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Monadic second-order model-checking on decomposable matroids ⋮ Algorithms for propositional model counting ⋮ Parameterized shifted combinatorial optimization ⋮ Boolean-width of graphs ⋮ Computing rank-width exactly ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Computing with Tangles ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Clique-width of point configurations ⋮ A SAT Approach to Branchwidth ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Boolean-Width of Graphs ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ Partial complementation of graphs ⋮ Revising Johnson's table for the 21st century ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More ⋮ Unnamed Item ⋮ Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming
This page was built for publication: Finding Branch-Decompositions and Rank-Decompositions
