Maximum k-covering of weighted transitive graphs with applications
DOI10.1007/BF01185340zbMATH Open0766.68103OpenAlexW1903290558MaRDI QIDQ1207331FDOQ1207331
Publication date: 1 April 1993
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01185340
network flowVLSI layoutinteger sequencestransitive graph\(k\)-layer topological via minimizationmaximum \(k\)-independent set of interval graphsmaximum increasing \(k\)- subsequencemaximum multidimensional \(k\)-chain
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Stochastic network models in operations research (90B15) Applications of graph theory to circuits and networks (94C15)
Cites Work
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Efficient algorithms for interval graphs and circular-arc graphs
- Algorithms for maximumk-colorings andk-coverings of transitive graphs
- On Comparability and Permutation Graphs
- A fast algorithm for computing longest common subsequences
- An Optimal Solution for the Channel-Assignment Problem
- Optimal Three-Layer Channel Routing
- An efficient algorithm for maxdominance, with applications
- Channel routing of multiterminal nets
- Channel routing in knock-knee mode: Simplified algorithms and proofs
- An Optimal Algorithm for the Maximum Two-Chain Problem
- Circular permutation graph family with applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (10)
- The just-in-time scheduling problem in a flow-shop scheduling system
- \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs
- Maximum weighted independent sets on transitive graphs and applications
- Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- Title not available (Why is that?)
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Optimal channel allocation for several types of cellular radio networks
- Just-in-time scheduling with controllable processing times on parallel machines
This page was built for publication: Maximum \(k\)-covering of weighted transitive graphs with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1207331)
