The $b$-\textsc{Matching} problem in distance-hereditary graphs and beyond

DOI10.1016/j.dam.2021.09.012zbMath1476.05166OpenAlexW3203589131MaRDI QIDQ2235279

Publication date: 21 October 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.09.012

zbMATH Keywords

distance-hereditary graphs split decomposition FPT in P maximum-cardinality matching $b$-\textsc{Matching}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
An $O(n)$ time algorithm for maximum matching in $P_{4}$-tidy graphs
Constrained multi-object auctions and $b$-matching
An O($n$) time algorithm for maximum matching on cographs
Solving some NP-complete problems using split decomposition
Distance-hereditary graphs
Finding a maximum matching in a circular-arc graph
Matching and multidimensional matching in chordal and strongly chordal graphs
Tractable combinatorial auctions and $b$-matching
Maximum matching in regular and almost regular graphs
LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
Linear Time Split Decomposition Revisited
TWO THEOREMS IN GRAPH THEORY
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Decomposition of Directed Graphs
Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
Data Structures for Weighted Matching and Extensions to b -matching and f -factors
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
On Computing the Nested Sums and Infimal Convolutions of Convex Piecewise-Linear Functions
Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
The Power of Linear-Time Data Reduction for Maximum Matching
BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
Paths, Trees, and Flowers
Fast approximation algorithms for the diameter and radius of sparse graphs
Maximum matching in a convex bipartite graph
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: The $b$-\textsc{Matching} problem in distance-hereditary graphs and beyond

The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond