scientific article

Publication date: 31 March 2011

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

discrete mathematics combinatorial optimization

Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Connectivity (05C40)

Related Items

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams, On the infinite Lucchesi–Younger conjecture I, Greedoids from flames, Packing of spanning mixed arborescences, On Packing Dijoins in Digraphs and Weighted Digraphs, The b‐bibranching problem: TDI system, packing, and discrete convexity, On a partition LP relaxation for min-cost 2-node connected spanning subgraphs, The complexity of 2-vertex-connected orientation in mixed graphs, Beating the Integrality Ratio for $s$-$t$-Tours in Graphs, Partitioning into common independent sets via relaxing strongly base orderability, FPT algorithms for packing $k$-safe spanning rooted sub(di)graphs, On 2-strong connectivity orientations of mixed graphs and related problems, Count and cofactor matroids of highly connected graphs, Popular critical matchings in the many-to-many setting, Integral packing of branchings in capacitaded digraphs, Improved approximation algorithms for single-tiered relay placement, Packing spanning trees and spanning 2-connected $k$-edge-connected essentially $(2k-1)$-edge-connected subgraphs, A characterisation of the generic rigidity of 2-dimensional point-line frameworks, Rainbow and monochromatic circuits and cocircuits in binary matroids, The Steiner Problem for Count Matroids, Sparse Graphs and an Augmentation Problem, Globally Rigid Augmentation of Rigid Graphs, An extension of Lehman's theorem and ideal set functions, Base polyhedra and the linking property, Matroids of gain graphs in applied discrete geometry, A 3/2-Approximation for the Metric Many-Visits Path TSP, Checking the admissibility of odd-vertex pairings is hard, Stronger bounds and faster algorithms for packing in generalized kernel systems, Algorithms for finding a rooted $(k,1)$-edge-connected orientation, Structured Connectivity Augmentation, Antistrong digraphs, Minimum Cuts and Sparsification in Hypergraphs, Submodular Functions: Learnability, Structure, and Optimization, Reachability in arborescence packings, Fair integral submodular flows, Plane augmentation of plane graphs to meet parity constraints, A simple algorithm and min-max formula for the inverse arborescence problem, A Discrete Convex Min-Max Formula for Box-TDI Polyhedra, Connectivity of orientations of 3-edge-connected graphs, An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem, Minimum-cost flow algorithms: an experimental evaluation, Structured Connectivity Augmentation, Simple push-relabel algorithms for matroids and submodular flows, A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case, The Generalized Terminal Backup Problem, Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design, Packing of arborescences with matroid constraints via matroid intersection, Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs, A generalized-polymatroid approach to disjoint common independent sets in two matroids, Analyzing Residual Random Greedy for monotone submodular maximization, The $b$-branching problem in digraphs, On the fixed-parameter tractability of the maximum connectivity improvement problem, Unnamed Item, Making Bipartite Graphs DM-Irreducible, Approximating Minimum Cost Connectivity Orientation and Augmentation, Graph orientations with set connectivity requirements, Path-contractions, edge deletions and connectivity preservation, Eulerian orientations and vertex-connectivity, Packing of maximal independent mixed arborescences, On the tractability of some natural packing, covering and partitioning problems, Minimum Cost Globally Rigid Subgraphs, Shorter tours by nicer ears: $7/5$-approximation for the graph-TSP, $3/2$ for the path version, and $4/3$ for two-edge-connected subgraphs, A faster algorithm for packing branchings in digraphs, A $4+\epsilon$ approximation for $k$-connected subgraphs, Old and new results on packing arborescences in directed hypergraphs, Envy-free matchings with lower quotas, Matchings under distance constraints. I, List Coloring of Two Matroids through Reduction to Partition Matroids, Blocking optimal structures, On orienting graphs for connectivity: Projective planes and Halin graphs, Graded sparse graphs and body-length-direction frameworks, Combinatorial optimization with interaction costs: complexity and solvable cases, Minimum weight connectivity augmentation for planar straight-line graphs, Subgraph polytopes and independence polytopes of count matroids, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Packing in generalized kernel systems: a framework that generalizes packing of branchings, Complexity of packing common bases in matroids, Maximum edge-disjoint paths in planar graphs with congestion 2, The $(2, k)$-connectivity augmentation problem: algorithmic aspects, On the global rigidity of tensegrity graphs, Mechanism design with costly verification and limited punishments, Packing of mixed hyperarborescences with flexible roots via matroid intersection, 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, Covering Intersecting Bi-set Families under Matroid Constraints, Pfaffian pairs and parities: counting on linear matroid intersection and parity problems, Upper and lower degree-constrained graph orientation with minimum penalty, On Maximal Independent Arborescence Packing, Unnamed Item, Computing in combinatorial optimization, Path-Contractions, Edge Deletions and Connectivity Preservation, Extended formulations of lower-truncated transversal polymatroids, On basic operations related to network induction of discrete convex functions, On integer network synthesis problem with tree-metric cost, Polymatroid-based capacitated packing of branchings, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, Integer plane multiflow maximisation: one-quarter-approximation and gaps, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on M-convex sets: algorithms and applications, Orientations and detachments of graphs with prescribed degrees and connectivity, Decomposition into two trees with orientation constraints, Relay placement for two-connectivity, Sparse hypergraphs with applications in combinatorial rigidity, Market Pricing for Matroid Rank Valuations, On the complexity of finding well-balanced orientations with upper bounds on the out-degrees, Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems, A sufficient connectivity condition for rigidity and global rigidity of linearly constrained frameworks in $\mathbb{R}^2$, Globally balancing spanning trees, Testing the supermodular-cut condition, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases, Approximation algorithms for connectivity augmentation problems, Degree-constrained graph orientation: maximum satisfaction and minimum violation, Sparse graphs and an augmentation problem, Gain-sparsity and symmetry-forced rigidity in the plane