Maximum matching in almost linear time on graphs of bounded clique-width
From MaRDI portal
Publication:2093582
Recommendations
- Maximum Matching in almost linear time on graphs of bounded clique-width
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- scientific article; zbMATH DE number 6850484
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- The \(b\)-matching problem in distance-hereditary graphs and beyond
Cites work
- A characterisation of clique-width through nested partitions
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
- A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
- A polynomial algorithm for b-matchings: An alternative approach
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A Short Proof of the Factor Theorem for Finite Graphs
- Algorithmic aspects of switch cographs
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- Algorithms for weighted matching generalizations. I: Bipartite graphs, b-matching, and unweighted f-factors
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
- An O(n) time algorithm for maximum matching on cographs
- Antisymmetrical Digraphs
- Approximating clique-width and branch-width
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Bipartite graphs totally decomposable by canonical decomposition
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Classifying the clique-width of \(H\)-free bipartite graphs
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Constrained-path labellings on graphs of bounded clique-width
- Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Efficient parameterized algorithms for computing all-pairs shortest paths
- Finding a maximum matching in a circular-arc graph
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Graph structure and monadic second-order logic. A language-theoretic approach
- Graph theory
- Graph theory
- scientific article; zbMATH DE number 3141016 (Why is no real title available?)
- scientific article; zbMATH DE number 1107732 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 795216 (Why is no real title available?)
- scientific article; zbMATH DE number 7489399 (Why is no real title available?)
- scientific article; zbMATH DE number 3220175 (Why is no real title available?)
- scientific article; zbMATH DE number 3232667 (Why is no real title available?)
- Intractability of clique-width parameterizations
- Kernelization lower bounds for finding constant-size subgraphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Matching Is as Easy as the Decision Problem, in the NC Model
- Matching theory
- Maximum matching in a convex bipartite graph
- Maximum matching in graphs with an excluded minor
- Maximum matching in regular and almost regular graphs
- Monadic second-order evaluations on tree-decomposable graphs
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On adaptive algorithms for maximum matching
- On the clique-width of graph with few \(P_{4}\)'s
- On the clique-width of some perfect graph classes
- On the power of tree-depth for fully polynomial FPT algorithms
- On the Relationship Between Clique-Width and Treewidth
- Paths, Trees, and Flowers
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Query efficient implementation of graphs of bounded clique-width
- Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
- Rank-width and vertex-minors
- Solving some NP-complete problems using split decomposition
- Subcubic equivalences between path, matrix, and triangle problems
- The \(b\)-matching problem in distance-hereditary graphs and beyond
- The Factorization of Linear Graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Power of Linear-Time Data Reduction for Maximum Matching
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- Tree acceptors and some of their applications
- Upper bounds to the clique width of graphs
Cited in
(7)- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- scientific article; zbMATH DE number 5799830 (Why is no real title available?)
- The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
- The \(b\)-matching problem in distance-hereditary graphs and beyond
- Maximum Matching in almost linear time on graphs of bounded clique-width
- Getting linear time in graphs of bounded neighborhood diversity
This page was built for publication: Maximum matching in almost linear time on graphs of bounded clique-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093582)
