On the computational complexity of the bipartizing matching problem
type: Item
instance of: scholarly article
title: On the computational complexity of the bipartizing matching problem
zbMATH Open document ID: 1497.05093
author: Dieter Rautenbach
author: Uéverton S. Souza
author: Carlos Vinícius G. C. Lima
author: Jayme L. Szwarcfiter
published in: Annals of Operations Research
publication date: 2022-09-26T00:00:00Z
full work available at URL: https://arxiv.org/abs/1710.07741
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 7592273
zbMATH Keywords: graph modification problems
zbMATH Keywords: edge bipartization
zbMATH Keywords: defective coloring
zbMATH Keywords: planar graphs
zbMATH Keywords: NP-completeness
zbMATH Keywords: parameterized complexity
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3130437458
arXiv ID: 1710.07741
cites work: Exploring the Kernelization Borders for Hitting Cycles
cites work: Hardness of edge-modification problems
cites work: Q3758854
cites work: Vertex-Coloring with Defects
cites work: Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
cites work: Degree-constrained 2-partitions of graphs
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Independent Feedback Vertex Set for P_5-free Graphs
cites work: On 1-improper 2-coloring of sparse graphs
cites work: New graph classes of bounded clique-width
cites work: Clique-width for 4-vertex forbidden subgraphs
cites work: Q5387674
cites work: NP-completeness results for edge modification problems
cites work: A new characterization of \(P_k\)-free graphs
cites work: Deadlock resolution in wait-for graphs by vertex/arc deletion
cites work: Graph Bipartization and via minimization
cites work: Editing graphs to satisfy diversity requirements
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Handbook of Graph Grammars and Computing by Graph Transformation
cites work: Q3077955
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
cites work: Defective coloring revisited
cites work: Parameterized Algorithms
cites work: Q3577833
cites work: Vertex partitions of graphs into cographs and stars
cites work: Fundamentals of parameterized complexity
cites work: Q4230860
cites work: On bipartization of cubic graphs by removal of an independent set
cites work: On the bipartite vertex frustration of graphs
cites work: Some simplified NP-complete graph problems
cites work: Partitions of graphs into cographs
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
cites work: Q3744180
cites work: Efficient Planarity Testing
cites work: Algorithmic meta-theorems for restrictions of treewidth
cites work: Decycling with a matching
cites work: Q5530470
cites work: Minimum-weight triangulation is NP-hard
cites work: Complexity classification of some edge modification problems
cites work: Q4560268
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: The complexity of satisfiability problems
cites work: All structured programs have small tree width and good register allocation
cites work: Node-and edge-deletion NP-complete problems
cites work: Edge-Deletion Problems
DOI: 10.1007/S10479-021-03966-9
Recommended article: Solving Matching Problems Efficiently in Bipartite Graphs
Recommended article: An efficient algorithm for the bipartite matching problem
Recommended article: Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem

On the computational complexity of the bipartizing matching problem (Recommended article)
Recommended article: Q4252363
Similarity Score: 0.90378976
Recommender Run: Recommender Run 3

On the computational complexity of the bipartizing matching problem (Recommended article)
Recommended article: On the Bipartite Unique Perfect Matching Problem
Similarity Score: 0.9011506
Recommender Run: Recommender Run 3

On the computational complexity of the bipartizing matching problem (Recommended article)
Recommended article: Q3646847
Similarity Score: 0.90084016
Recommender Run: Recommender Run 3

On the computational complexity of the bipartizing matching problem (Recommended article)
Recommended article: On maximum bipartite matching with separation
Similarity Score: 0.8996783
Recommender Run: Recommender Run 3

On the computational complexity of the bipartizing matching problem (Recommended article)
Recommended article: On the Robust Communication Complexity of Bipartite Matching
Similarity Score: 0.8991699
Recommender Run: Recommender Run 3

On the computational complexity of the bipartizing matching problem (Recommended article)
Recommended article: Parallel algorithms for bipartite matching problems on distributed memory computers
Similarity Score: 0.89656866
Recommender Run: Recommender Run 3