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
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
Linear programming (90C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Boolean programming (90C09)
Cites Work
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- Linear time solvable optimization problems on graphs of bounded clique-width
- Polynomial algorithms in linear programming
- Toeplitz and circulant matrices: a review.
- Integer program with bimodular matrix
- Edge dominating set and colorings on graphs with fixed clique-width
- On linear and circular structure of (claw, net)-free graphs
- Critical properties of graphs of bounded clique-width
- A note on non-degenerate integer programs with small sub-determinants
- A strongly polynomial algorithm for bimodular integer linear programming
Cited In (8)
- Combinatorial bounds via measure and conquer
- An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
- Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
- On lattice point counting in \(\varDelta\)-modular polyhedra
- FPT-algorithm for computing the width of a simplex given by a convex hull
- On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- A fixed-parameter tractable algorithm for matrix domination
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)
