Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs

DOI10.1137/140980053zbMath1338.05052OpenAlexW3021340860MaRDI QIDQ2813347

Mourad Baïou, Francisco Barahona

Publication date: 23 June 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140980053

zbMATH Keywords

NP-completenesspolynomial algorithmbalancing signed graphsmaximum induced acyclic subgraphmaximum induced bipartite subgraph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (1)

Graph Bipartization Problem with Applications to Via Minimization in VLSI Design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• On cuts and matchings in planar graphs
• Retiming synchronous circuitry
• Facets of the balanced (acyclic) induced subgraph polytope
• How to make a digraph strongly connected
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Approximating minimum feedback sets and multicuts in directed graphs
• Graph Bipartization and via minimization
• A Separator Theorem for Planar Graphs
• An algorithm for the single machine sequencing problem with precedence constraints
• On Odd Cuts and Plane Multicommodity Flows
• Planar Formulae and Their Uses
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• A Minimax Theorem for Directed Graphs
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• A polyhedral approach to the feedback vertex set problem
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• Matching, Euler tours and the Chinese postman
• Centroids, Representations, and Submodular Flows
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Reducibility among Combinatorial Problems
• Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs

This page was built for publication: Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs