Graph Bipartization Problem with Applications to Via Minimization in VLSI Design

DOI10.1142/S0129054122500198OpenAlexW4287219802MaRDI QIDQ6132388FDOQ6132388

Authors: Lan Lin, Yixun Lin 

Publication date: 16 August 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054122500198

zbMATH Keywords

polynomial-time algorithmVLSI designvia minimizationbipartite induced subgraphodd-cycle transversal

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Graph theory
• Finding odd cycle transversals.
• Algorithmic graph theory and perfect graphs
• Combinatorial optimization. Theory and algorithms.
• Planar graph bipartization in linear time
• Graph Bipartization and via minimization
• Title not available (Why is that?)
• Faster graph bipartization
• Title not available (Why is that?)
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Title not available (Why is that?)
• Maximum bipartite subgraph of geometric intersection graphs
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs

Cited In (4)

• Title not available (Why is that?)
• Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays
• Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments
• Title not available (Why is that?)

This page was built for publication: Graph Bipartization Problem with Applications to Via Minimization in VLSI Design

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