A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
From MaRDI portal
Cites work
- \(k\)-NLC graphs and polynomial algorithms
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Approximating clique-width and branch-width
- Approximating rank-width and clique-width quickly
- Clique-width is NP-complete
- Computing the chromatic number using graph decompositions via matrix rank
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Fast Hamiltonicity checking via bases of perfect matchings
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Finer tight bounds for coloring on clique-width
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Known algorithms on graphs of bounded treewidth are probably optimal
- Linear time solvable optimization problems on graphs of bounded clique-width
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Matching is as easy as matrix inversion
- Model checking lower bounds for simple graphs
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- On the equivalence among problems of bounded width
- Optimal dynamic program for r-domination problems over tree decompositions
- Polynomial-time recognition of clique-width 3 graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Structurally parameterized \(d\)-scattered set
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Tight algorithms for connectivity problems parameterized by clique-width
- Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
- Tight bounds for connectivity problems parameterized by cutwidth
- Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- Upper bounds to the clique width of graphs
- Vertex disjoint paths on clique-width bounded graphs
Cited in
(2)
This page was built for publication: A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875179)
