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
NP-completenesspolynomial algorithmbalancing signed graphsmaximum induced acyclic subgraphmaximum induced bipartite subgraph
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)
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
