On a graph partition problem with application to VLSI layout
DOI10.1016/0020-0190(92)90017-PzbMATH Open0764.68132OpenAlexW2019683022MaRDI QIDQ1199941FDOQ1199941
Authors: Arunabha Sen, Haiyong Deng, Sumanta Guha 
Publication date: 17 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90017-p
Recommendations
graph partitionlinear programminginterval graphsNP-completepermutation graphspolynomial time algorithmperfect graphsVLSI layoutcircle graphchromatic sum
Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Circuits, networks (94C99) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Applications of graph theory to circuits and networks (94C15)
Cites Work
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization
- Title not available (Why is that?)
- On certain polytopes associated with graphs
- Title not available (Why is that?)
- Finding a maximum independent set in a permutation graph
- Parallel concepts in graph theory
- Permutation Graphs and Transitive Graphs
- Perfect zero–one matrices
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- The NP-completeness column: an ongoing guide
Cited In (37)
- Minimum sum coloring problem: upper bounds for the chromatic strength
- Computing lower bounds for minimum sum coloring and optimum cost chromatic partition
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- An optimal parallel algorithm forc-vertex-ranking of trees
- Rank numbers for bent ladders
- ILP models and column generation for the minimum sum coloring problem
- Finding the edge ranking number through vertex partitions
- Rankings of graphs
- Title not available (Why is that?)
- Graphs whose \(l_p\)-optimal rankings are \(l_{\infty}\) optimal
- Minimal \(k\)-rankings and the rank number of \(P^2_n\)
- NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
- Vertex ranking of asteroidal triple-free graphs
- Vertex ranking of asteroidal triple-free graphs
- Fully dynamic algorithms for permutation graph coloring
- On finding separators in temporal split and permutation graphs
- On finding separators in temporal split and permutation graphs
- Approximation results for the optimum cost chromatic partition problem
- On vertex ranking of a starlike graph
- Constructing a minimum height elimination tree of a tree in linear time
- Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays
- Hitting sets online and unique-MAX coloring
- Sum coloring and interval graphs: A tight upper bound for the minimum number of colors
- Title not available (Why is that?)
- A framework for solving VLSI graph layout problems
- Maximizing the number of edges in optimal \(k\)-rankings
- Max-optimal and sum-optimal labelings of graphs
- Minimal rankings and the arank number of a path
- Title not available (Why is that?)
- An optimal parallel algorithm for node ranking of cographs
- \(l_p\)-optimal rankings and max-optimal rankings are different
- Tree partitioning under constraints. -- Clustering for vehicle routing problems
- A branch-and-price algorithm for the minimum sum coloring problem
- The optimal cost chromatic partition problem for trees and interval graphs
- Graph partitioning applied to the logic testing of combinational circuits
- Rank numbers for some trees and unicyclic graphs
- Approximation Results for the Optimum Cost Chromatic Partition Problem
This page was built for publication: On a graph partition problem with application to VLSI layout
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199941)
