Packing directed circuits fractionally
From MaRDI portal
Publication:1894706
DOI10.1007/BF01200760zbMath0826.05031OpenAlexW2040831377MaRDI QIDQ1894706
Publication date: 26 November 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200760
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)
Related Items (48)
On the Complexity of Singly Connected Vertex Deletion ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Unnamed Item ⋮ Feedback arc set problem in bipartite tournaments ⋮ Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Testing Consumer Rationality Using Perfect Graphs and Oriented Discs ⋮ Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Hardness of fully dense problems ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Packing directed cycles efficiently ⋮ Packing directed circuits ⋮ Aligning and Labeling Genomes under the Duplication-Loss Model ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ The multi-multiway cut problem ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks ⋮ Approximating minimum feedback sets and multi-cuts in directed graphs ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ Positive and negative cycles in Boolean networks ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ Approximability of Packing Disjoint Cycles ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Understanding planning with incomplete information and sensing ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Target set selection for conservative populations ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ Approximability of packing disjoint cycles ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Unnamed Item ⋮ Approximation algorithms for the Bipartite Multicut problem ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Combinatorial algorithms for feedback problems in directed graphs ⋮ Unnamed Item ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ A unified approximation algorithm for node-deletion problems ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Models for concurrent product and process design ⋮ Tournaments and Semicomplete Digraphs ⋮ On the complexity of singly connected vertex deletion ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
Cites Work
This page was built for publication: Packing directed circuits fractionally
