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

DOI10.1016/J.DISOPT.2018.03.002zbMATH Open1506.05160OpenAlexW2795518735WikidataQ130041840 ScholiaQ130041840MaRDI QIDQ1662648FDOQ1662648

Authors Dimitry V. Gribanov, D. 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

dominating set problemefficient algorithmmatrix minorBoolean linear programming

Mathematics Subject Classification ID

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

Recommendations

• The computational complexity of three graph problems for instances with bounded minors of constraint matrices
• A decidability result for the dominating set problem
• On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
• Dominating sets in perfect graphs
• A complexity dichotomy and a new boundary class for the dominating set problem

Cites work

• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• A new polynomial-time algorithm for linear programming
• A note on non-degenerate integer programs with small sub-determinants
• A strongly polynomial algorithm for bimodular integer linear programming
• Critical properties of graphs of bounded clique-width
• Edge dominating set and colorings on graphs with fixed clique-width
• Integer program with bimodular matrix
• Linear time solvable optimization problems on graphs of bounded clique-width
• On linear and circular structure of (claw, net)-free graphs
• Polynomial algorithms in linear programming
• Toeplitz and circulant matrices: a review.

Cited in

(10)

• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
• A fixed-parameter tractable algorithm for matrix domination
• Combinatorial bounds via measure and conquer
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• On lattice point counting in \(\varDelta\)-modular polyhedra
• FPT-algorithm for computing the width of a simplex given by a convex hull
• The complexity of some graph problems with bounded minors of their constraint matrices
• On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size

This page was built for publication: The computational complexity of dominating set problems for instances with bounded minors of constraint matrices

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