On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

DOI10.1016/J.DISC.2004.08.042zbMATH Open1079.68073OpenAlexW2085311936MaRDI QIDQ2484367FDOQ2484367

Authors: Martin Charles Golumbic, Elad Verbin, Haim Kaplan 

Publication date: 1 August 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.08.042

Recommendations

• scientific article; zbMATH DE number 3904502
• Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Parallel algorithms for permutation graphs
• Circular permutation graph family with applications

zbMATH Keywords

VLSI layoutDynamic programmingPermutation graphsMultiprocessor schedulingClique numberCell flippingIndependent set numberStable set number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• Approximation algorithms for scheduling unrelated parallel machines
• Some Matching Problems for Bipartite Graphs
• On computing the length of longest increasing subsequences
• The Multiple-Choice Knapsack Problem
• Scheduling unit-time jobs on processors with different capabilities
• Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
• On a scheduling problem where a job can be executed only by a limited number of processors

This page was built for publication: On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

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