On a graph partition problem with application to VLSI layout

DOI10.1016/0020-0190(92)90017-PzbMath0764.68132OpenAlexW2019683022MaRDI QIDQ1199941

Haiyong Deng, Arunabha Sen, Sumantha 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

zbMATH Keywords

linear programmingpolynomial time algorithmperfect graphsNP-completeinterval graphspermutation graphsVLSI layoutgraph partitioncircle graphchromatic sum

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Circuits, networks (94C99) Coloring of graphs and hypergraphs (05C15) Applications of graph theory to circuits and networks (94C15)

Related Items (27)

An optimal parallel algorithm forc-vertex-ranking of trees ⋮ Vertex ranking of asteroidal triple-free graphs ⋮ NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem ⋮ Approximation results for the optimum cost chromatic partition problem ⋮ Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ Maximizing the number of edges in optimal \(k\)-rankings ⋮ \(l_p\)-optimal rankings and max-optimal rankings are different ⋮ Rankings of graphs ⋮ Finding the edge ranking number through vertex partitions ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Tree partitioning under constraints. -- Clustering for vehicle routing problems ⋮ Rank numbers for bent ladders ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ ILP models and column generation for the minimum sum coloring problem ⋮ Computing lower bounds for minimum sum coloring and optimum cost chromatic partition ⋮ Minimal \(k\)-rankings and the rank number of \(P^2_n\) ⋮ Minimal rankings and the arank number of a path ⋮ Rank numbers for some trees and unicyclic graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ Hitting sets online and unique-MAX coloring ⋮ On finding separators in temporal split and permutation graphs ⋮ An optimal parallel algorithm for node ranking of cographs ⋮ Max-optimal and sum-optimal labelings of graphs ⋮ Sum coloring and interval graphs: A tight upper bound for the minimum number of colors ⋮ Fully dynamic algorithms for permutation graph coloring ⋮ On vertex ranking of a starlike graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Finding a maximum independent set in a permutation graph
• Geometric algorithms and combinatorial optimization
• Parallel concepts in graph theory
• On certain polytopes associated with graphs
• The NP-completeness column: an ongoing guide
• Perfect zero–one matrices
• Permutation Graphs and Transitive Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: On a graph partition problem with application to VLSI layout