A Polyhedral Description of Kernels

DOI10.1287/moor.2015.0764zbMath1342.90105OpenAlexW2332359412MaRDI QIDQ3186539

Wenan Zang, Qin Chen, Xu-jin Chen

Publication date: 10 August 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10722/231992

zbMATH Keywords

complexityalgorithmdigraphpolytopekernel

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on kernels and Sperner's Lemma
• Perfect graphs are kernel solvable
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Extending kernel perfect digraphs to kernel perfect critical digraphs
• Characterization of stable matchings as extreme points of a polytope
• Fractional kernels in digraphs
• Solutions of irreflexive relations
• Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron
• An efficient algorithm for the “stable roommates” problem
• Planar Formulae and Their Uses

This page was built for publication: A Polyhedral Description of Kernels