On the acyclic subgraph polytope
From MaRDI portal
Publication:3698818
DOI10.1007/BF01582009zbMath0577.05034OpenAlexW2042649619WikidataQ29042437 ScholiaQ29042437MaRDI QIDQ3698818
Martin Grötschel, Michael Jünger, Gerhard Reinelt
Publication date: 1985
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582009
algorithmsdigraphpolynomial timefacets of polyhedrafeedback arc set problemacyclic subgraph problemacyclic subgraph polytopeweakly acyclic digraphs
Integer programming (90C10) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Polytopes and polyhedra (52Bxx)
Related Items
More facets from fences for linear ordering and acyclic subgraph polytopes, Facets of the linear ordering polytope, Approximations for the maximum acyclic subgraph problem, Polyhedral structure and properties of a model for layout design, Acyclic Orientations with Path Constraints, On computing the path number of a graph, The reversing number of a digraph, Least cost influence propagation in (social) networks, A survey on the linear ordering problem for weighted or unweighted tournaments, On the partial order polytope of a digraph, On cutting-plane proofs in combinatorial optimization, Facets and lifting procedures for the set covering polytope, Tight Localizations of Feedback Sets, An Exact Method for the Minimum Feedback Arc Set Problem, Combinatorial acyclicity models for potential‐based flows, A branch‐and‐cut approach for the least cost influence problem on social networks, On the membership problem for the \({0, 1/2}\)-closure, A branch-and-bound algorithm for the linear ordering problem with cumulative costs, Facet Generating Techniques, On approximability of linear ordering and related NP-optimization problems on graphs., Computational results of an interior point algorithm for large scale linear programming, Generalizing the concept of binary choice systems induced by rankings: One way of probabilizing deterministic measurement structures, Geometric and combinatorial properties of the polytope of binary choice probabilities, A branch-and-cut algorithm for a resource-constrained scheduling problem, On a composition of independence systems by circuit identification, The strongest facets of the acyclic subgraph polytope are unknown, Transitive packing, A polyhedral approach to the feedback vertex set problem, Integer linear programming for the Bayesian network structure learning problem, Arc-based integer programming formulations for three variants of proportional symbol maps, A graph-theoretic heuristic for designing loop-layout manufacturing systems, The linear ordering problem with cumulative costs, Multiprocessor scheduling under precedence constraints: polyhedral results, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Facets of the linear ordering polytope: a unification for the fence family through weighted graphs, Median linear orders: Heuristics and a branch and bound algorithm, Exact localisations of feedback sets, How to recycle your facets, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, A new heuristic algorithm solving the linear ordering problem, On the linear ordering problem and the rankability of data, Computing in combinatorial optimization, Workload balancing and loop layout in the design of a flexible manufacturing system, Optimal facility layout design, Unnamed Item, Signed orders, choice probabilities, and linear polytopes, Computing Optimal Discrete Morse Functions, A polyhedral approach to least cost influence maximization in social networks
Cites Work
