Finding Branch-Decompositions and Rank-Decompositions
From MaRDI portal
Publication:5902074
DOI10.1137/070685920zbMath1163.05331MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Unnamed Item, Covering Vectors by Spaces: Regular Matroids, A Simpler Self-reduction Algorithm for Matroid Path-Width, Finding Branch-Decompositions of Matroids, Hypergraphs, and More, Finding branch-decompositions of matroids, hypergraphs, and more, Parameterized Complexity of Safe Set, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., Partial complementation of graphs, Inductive computations on graphs defined by clique-width expressions, Parameterized algorithms for the happy set problem, Parameterized shifted combinatorial optimization, 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, Clique-width of point configurations, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, Tangle bases: Revisited, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, On the model-checking of monadic second-order formulas with edge set quantifications, Decomposition width of matroids, Well-quasi-ordering of matrices under Schur complement and applications to directed graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Monadic second-order model-checking on decomposable matroids, Compact labelings for efficient first-order model-checking, Boolean-width of graphs, Meta-kernelization with structural parameters, \(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, Computing rank-width exactly, Solving problems on graphs of high rank-width, Automata for the verification of monadic second-order graph properties, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Revising Johnson's table for the 21st century, Subgraph complementation, Structural parameters for scheduling with assignment restrictions, Branch-depth: generalizing tree-depth of graphs, Algorithms for propositional model counting, The rank-width of edge-coloured graphs, Rank-width: algorithmic and structural results, Meta-kernelization using well-structured modulators, Digraph width measures in parameterized algorithmics, Latency-bounded target set selection in social networks, Computing densest \(k\)-subgraph with structural parameters, A SAT Approach to Branchwidth, Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Finding Good Decompositions for Dynamic Programming on Dense Graphs, Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory, $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs, Digraphs of Bounded Width, Unnamed Item, Containment of Monadic Datalog Programs via Bounded Clique-Width, Solving Problems on Graphs of High Rank-Width, Boolean-Width of Graphs, On Digraph Width Measures in Parameterized Algorithmics
