Reliable assignments of processors to tasks and factoring on matroids

DOI10.1016/0012-365X(93)90360-6zbMath0796.68027OpenAlexW2139768824MaRDI QIDQ685664

Charles J. Colbourn, Ehab S. El-Mallah

Publication date: 24 October 1993

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

Full work available at URL: https://doi.org/10.1016/0012-365x(93)90360-6

zbMATH Keywords

complexityreliabilityassignmenttransversal matroid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of matroids and geometric lattices (05B35) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (2)

Blocking optimal arborescences ⋮ The complexity of computing the Tutte polynomial on transversal matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroids and linking systems
• The complexity of completing partial Latin squares
• Matching theory
• Matroid Steiner problems, the Tutte polynomial and network reliability
• Edge-packings of graphs and network reliability
• Gammoids and transversal matroids
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks
• A Survey of Network Reliability and Domination Theory
• A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability
• Counting almost minimum cutsets with reliability applications
• The NP-Completeness of Some Edge-Partition Problems
• On Fundamental Transversal Matroids
• The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
• Bounds on the Reliability Polynomial for Shellable Independence Systems
• Network reliability and the factoring theorem
• Minimum partition of a matroid into independent subsets
• A Combinatorial Model for Series-Parallel Networks
• Strict Gammoids and Rank Functions
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Reliable assignments of processors to tasks and factoring on matroids