The computational complexity of dominating set problems for instances with bounded minors of constraint matrices

DOI10.1016/j.disopt.2018.03.002zbMath1506.05160OpenAlexW2795518735MaRDI QIDQ1662648

Dimitry V. Gribanov, Dmitriy S. Malyshev

Publication date: 20 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2018.03.002

zbMATH Keywords

efficient algorithmdominating set problemmatrix minorBoolean linear programming

Mathematics Subject Classification ID

Linear programming (90C05) Boolean programming (90C09) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On lattice point counting in \(\varDelta\)-modular polyhedra, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, FPT-algorithm for computing the width of a simplex given by a convex hull, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Integer program with bimodular matrix
• On linear and circular structure of (claw, net)-free graphs
• A note on non-degenerate integer programs with small sub-determinants
• Edge dominating set and colorings on graphs with fixed clique-width
• Critical properties of graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Polynomial algorithms in linear programming
• A strongly polynomial algorithm for bimodular integer linear programming