Graph Bipartization and via minimization
From MaRDI portal
Publication:3833614
DOI10.1137/0402004zbMath0677.68036OpenAlexW2012357906MaRDI QIDQ3833614
Hyeong-Ah Choi, Chong S. Rim, Kazuo Nakajima
Publication date: 1989
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1903/4706
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (20)
On bipartization of cubic graphs by removal of an independent set ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ Negative (and positive) circles in signed graphs: a problem collection ⋮ A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ On the computational complexity of the bipartizing matching problem ⋮ Inductive graph invariants and approximation algorithms ⋮ Graph Bipartization Problem with Applications to Via Minimization in VLSI Design ⋮ Solving VLSI design and DNA sequencing problems using bipartization of graphs ⋮ Polyhedral results for the bipartite induced subgraph problem ⋮ Strong matching preclusion ⋮ The maximum \(k\)-colorable subgraph problem and orbitopes ⋮ New bounds for the signless Laplacian spread ⋮ Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs ⋮ The critical node detection problem in networks: a survey ⋮ Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Faster graph bipartization ⋮ Distance in stratified graphs ⋮ A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis ⋮ Conditional matching preclusion for hypercube-like interconnection networks
This page was built for publication: Graph Bipartization and via minimization
