Restricted Bipartite Graphs: Comparison and Hardness Results

DOI10.1007/978-3-319-07956-1_22MaRDI QIDQ5251649zbMATH OpenOpenAlexFDO

Authors Tian Liu

Publication date 20 May 2015

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-07956-1_22

zbMATH Keywords

treewidthNP-completenessfeedback vertex setchordal bipartite graphstree convex bipartite graphsperfect elimination bipartite graphsconvex bipartite graphscircular convex bipartite graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Recommendations

• Restricted \(t\)-matchings in bipartite graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Tractable connected domination for restricted bipartite graphs
• On the complexity of construction of complete and complete bipartite graphs
• Tractable connected domination for restricted bipartite graphs (extended abstract)
• Restricted \(b\)-matchings in degree-bounded graphs
• Restricted edge-colourings of bipartite graphs

Cited in

(11)

• Solving problems on generalized convex graphs via mim-width
• Induced Matching in Some Subclasses of Bipartite Graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Domination in some subclasses of bipartite graphs
• Maximum Edge Bicliques in Tree Convex Bipartite Graphs
• Solving problems on generalized convex graphs via mim-width
• Maximum weight induced matching in some subclasses of bipartite graphs
• Constrained representations of map graphs and half-squares
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• An FPTAS for the hardcore model on random regular bipartite graphs
• Union closed tree convex sets

This page was built for publication: Restricted Bipartite Graphs: Comparison and Hardness Results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251649)