Minimal edge-coverings of pairs of sets

DOI10.1006/jctb.1995.1044zbMath0830.05051OpenAlexW1988132050MaRDI QIDQ1898731

Tibor Jordán, András Frank

Publication date: 20 September 1995

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/da2e1470fad646855ec927492a1c7a94490c6b48

zbMATH Keywords

digraphedge-connectivity augmentation theoremedge-coveringsmax-min theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (44)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating subset \(k\)-connectivity problems ⋮ Combinatorial algorithms for matchings, even factors and square-free 2-factors ⋮ A note on the vertex-connectivity augmentation problem ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ How to make a strongly connected digraph two-connected ⋮ A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs ⋮ Complexity of (arc)-connectivity problems involving arc-reversals or deorientations ⋮ Making a tournament k $k$‐strong ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems ⋮ Approximating node-connectivity augmentation problems ⋮ Making Bipartite Graphs DM-Irreducible ⋮ Restricted \(t\)-matchings in bipartite graphs ⋮ A Survey on Covering Supermodular Functions ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ On shredders and vertex connectivity augmentation ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ Degree constrained node-connectivity problems ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Jump Number of Two-Directional Orthogonal Ray Graphs ⋮ Strongly connectable digraphs and non-transitive dice ⋮ An algorithm to increase the node-connectivity of a digraph by one ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Local edge-connectivity augmentation in hypergraphs is NP-complete ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems ⋮ Independence free graphs and vertex connectivity augmentation ⋮ Augmenting trees so that every three vertices lie on a cycle ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Extremal graphs in connectivity augmentation ⋮ Complexity of packing common bases in matroids ⋮ The \((2, k)\)-connectivity augmentation problem: algorithmic aspects ⋮ Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings ⋮ Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation ⋮ Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs ⋮ Inapproximability of survivable networks ⋮ Path-Contractions, Edge Deletions and Connectivity Preservation ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Tournaments and Semicomplete Digraphs ⋮ Decreasing minimization on M-convex sets: algorithms and applications ⋮ Finding minimum generators of path systems

This page was built for publication: Minimal edge-coverings of pairs of sets