Maximum matching in almost linear time on graphs of bounded clique-width (Q2093582)

scientific article; zbMATH DE number 7608297

Language	Label	Description	Also known as
English	Maximum matching in almost linear time on graphs of bounded clique-width	scientific article; zbMATH DE number 7608297

Statements

instance of

scholarly article

0 references

title

Maximum matching in almost linear time on graphs of bounded clique-width (English)

0 references

0 references

0 references

27 October 2022

0 references

MaRDI profile type

Publication

0 references

full work available at URL

https://doi.org/10.1007/s00453-022-00999-9

0 references

cites work

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

0 references

Matching Is as Easy as the Decision Problem, in the NC Model

0 references

A polynomial algorithm for b-matchings: An alternative approach

0 references

Parameterized aspects of triangle enumeration

0 references

Q3258698

0 references

Q5422499

0 references

Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility

0 references

Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory

0 references

Algorithmic aspects of switch cographs

0 references

On the Relationship Between Clique-Width and Treewidth

0 references

Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs

0 references

The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

0 references

Q3077955

0 references

A characterisation of clique-width through nested partitions

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Monadic second-order evaluations on tree-decomposable graphs

0 references

Upper bounds to the clique width of graphs

0 references

Constrained-path labellings on graphs of bounded clique-width

0 references

Query efficient implementation of graphs of bounded clique-width

0 references

Classifying the clique-width of $H$-free bipartite graphs

0 references

Matching and multidimensional matching in chordal and strongly chordal graphs

0 references

Q3577833

0 references

Tree acceptors and some of their applications

0 references

A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path

0 references

Q4373681

0 references

Q5062015

0 references

Q5091021

0 references

The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes

0 references

Paths, Trees, and Flowers

0 references

Q4448752

0 references

Kernelization lower bounds for finding constant-size subgraphs

0 references

Intractability of Clique-Width Parameterizations

0 references

Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width

0 references

Clique-width III

0 references

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth

0 references

BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION

0 references

An $O(n)$ time algorithm for maximum matching in $P_{4}$-tidy graphs

0 references

A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width

0 references

Data Structures for Weighted Matching and Extensions to b -matching and f -factors

0 references

Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors

0 references

Q5520564

0 references

Q5508779

0 references

Q4845365

0 references

Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs

0 references

Maximum matching in a convex bipartite graph

0 references

ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

0 references

Characterizing multiterminal flow networks and computing flows in networks of small treewidth

0 references

Q5091230

0 references

On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

0 references

Efficient and Adaptive Parameterized Algorithms on Modular Decompositions

0 references

Q5874311

0 references

Finding a maximum matching in a circular-arc graph

0 references

Q3395507

0 references

ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S

0 references

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs

0 references

The Power of Linear-Time Data Reduction for Maximum Matching

0 references

Rank-width and vertex-minors

0 references

Approximating clique-width and branch-width

0 references

Solving some NP-complete problems using split decomposition

0 references

A polynomial-time algorithm, based on Newton's method, for linear programming

0 references

Generalized finite automata theory with an application to a decision problem of second-order logic

0 references

The Factorization of Linear Graphs

0 references

A Short Proof of the Factor Theorem for Finite Graphs

0 references

Antisymmetrical Digraphs

0 references

Subcubic Equivalences Between Path, Matrix, and Triangle Problems

0 references

An O($n$) time algorithm for maximum matching on cographs

0 references

Maximum matching in regular and almost regular graphs

0 references

Q2934588

0 references

Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs

0 references

Identifiers

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

10.1007/S00453-022-00999-9

0 references

Sitelinks

Mathematics(1 entry)

mardi Maximum matching in almost linear time on graphs of bounded clique-width