Maximum matching in almost linear time on graphs of bounded clique-width
type: Item
instance of: scholarly article
title: Maximum matching in almost linear time on graphs of bounded clique-width
author: Guillaume Ducoffe
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608297
MaRDI profile type: Publication
full work available at URL: s00453-022-00999-9
OpenAlex ID: W4283780304
cites work: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
cites work: Matching Is as Easy as the Decision Problem, in the NC Model
cites work: A polynomial algorithm for b-matchings: An alternative approach
cites work: Parameterized aspects of triangle enumeration
cites work: Q3258698
cites work: Q5422499
cites work: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
cites work: Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
cites work: Algorithmic aspects of switch cographs
cites work: On the Relationship Between Clique-Width and Treewidth
cites work: Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q3077955
cites work: A characterisation of clique-width through nested partitions
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Upper bounds to the clique width of graphs
cites work: Constrained-path labellings on graphs of bounded clique-width
cites work: Query efficient implementation of graphs of bounded clique-width
cites work: Classifying the clique-width of \(H\)-free bipartite graphs
cites work: Matching and multidimensional matching in chordal and strongly chordal graphs
cites work: Q3577833
cites work: Tree acceptors and some of their applications
cites work: A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
cites work: Q4373681
cites work: Q5062015
cites work: Q5091021
cites work: The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
cites work: Paths, Trees, and Flowers
cites work: Q4448752
cites work: Kernelization lower bounds for finding constant-size subgraphs
cites work: Intractability of Clique-Width Parameterizations
cites work: Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
cites work: Clique-width III
cites work: Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
cites work: BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
cites work: An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
cites work: A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
cites work: Data Structures for Weighted Matching and Extensions to b -matching and f -factors
cites work: Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors
cites work: Q5520564
cites work: Q5508779
cites work: Q4845365
cites work: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
cites work: Maximum matching in a convex bipartite graph
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Characterizing multiterminal flow networks and computing flows in networks of small treewidth
cites work: Q5091230
cites work: On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
cites work: Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
cites work: Q5874311
cites work: Finding a maximum matching in a circular-arc graph
cites work: Q3395507
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
cites work: The Power of Linear-Time Data Reduction for Maximum Matching
cites work: Rank-width and vertex-minors
cites work: Approximating clique-width and branch-width
cites work: Solving some NP-complete problems using split decomposition
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
cites work: The Factorization of Linear Graphs
cites work: A Short Proof of the Factor Theorem for Finite Graphs
cites work: Antisymmetrical Digraphs
cites work: Subcubic Equivalences Between Path, Matrix, and Triangle Problems
cites work: An O(\(n\)) time algorithm for maximum matching on cographs
cites work: Maximum matching in regular and almost regular graphs
cites work: Q2934588

Maximum matching in almost linear time on graphs of bounded clique-width (cites work)
cites work: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs

Maximum matching in almost linear time on graphs of bounded clique-width (Wikidata QID)
Wikidata QID: Q114229326

Maximum matching in almost linear time on graphs of bounded clique-width (DOI)
DOI: 10.1007/S00453-022-00999-9