Acyclic orientations with path constraints

DOI10.1051/RO:2008028MaRDI QIDQ3163668zbMATH OpenOpenAlexFDO

Authors Valmir C. Barbosa, Rosa Figueiredo, Nelson Maculan, Cid Carvalho de Souza

Publication date 26 October 2010

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/105414

zbMATH Keywords

acyclic orientationscombinatorial optimization problemsfacets of polyhedrapath constraints

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A polyhedral study of the acyclic coloring problem
• scientific article; zbMATH DE number 3888925
• Optimization problems on acyclic orientations of graphs, shellability of simplicial complexes, and acyclic partitions
• A polyhedral study of the acyclic coloring problem
• Facets based on cycles and cliques for the acyclic coloring polytope

Cites work

• Acyclic orientations of a graph and the chromatic and independence numbers
• Facets of the linear ordering polytope
• scientific article; zbMATH DE number 1107721 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Nombre chromatique et plus longs chemins d'un graphe
• On the acyclic subgraph polytope

Cited in

(9)

• A geometric approach to acyclic orientations
• Symmetry-breaking inequalities for ILP with structured sub-symmetry
• A note on orientation and chromatic number of graphs
• Optimization problems on acyclic orientations of graphs, shellability of simplicial complexes, and acyclic partitions
• Characterizing acyclic graphs by labeling edges
• A branch-and-cut algorithm for partition coloring
• Facets based on cycles and cliques for the acyclic coloring polytope
• On the Complexity of Universality for Partially Ordered NFAs
• Acyclic Orientation of Drawings

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: Acyclic orientations with path constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3163668)