Maximum \(k\)-covering of weighted transitive graphs with applications

DOI10.1007/BF01185340zbMath0766.68103OpenAlexW1903290558MaRDI QIDQ1207331

R. D. Lou, Majid Sarrafzadeh

Publication date: 1 April 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185340

zbMATH Keywords

integer sequencesnetwork flowtransitive graphVLSI layout\(k\)-layer topological via minimizationmaximum \(k\)-independent set of interval graphsmaximum increasing \(k\)- subsequencemaximum multidimensional \(k\)-chain

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Applications of graph theory to circuits and networks (94C15)

Related Items (7)

A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Optimal channel allocation for several types of cellular radio networks ⋮ Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey ⋮ The just-in-time scheduling problem in a flow-shop scheduling system ⋮ Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems ⋮ Just-in-time scheduling with controllable processing times on parallel machines

Cites Work

• Channel routing in knock-knee mode: Simplified algorithms and proofs
• An efficient algorithm for maxdominance, with applications
• Circular permutation graph family with applications
• Optimal Three-Layer Channel Routing
• On Comparability and Permutation Graphs
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• An Optimal Solution for the Channel-Assignment Problem
• Efficient algorithms for interval graphs and circular-arc graphs
• An Optimal Algorithm for the Maximum Two-Chain Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A fast algorithm for computing longest common subsequences
• Channel routing of multiterminal nets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum \(k\)-covering of weighted transitive graphs with applications