The computational complexity of three graph problems for instances with bounded minors of constraint matrices
DOI10.1016/J.DAM.2017.04.025zbMATH Open1365.05220OpenAlexW2608835862MaRDI QIDQ2357129FDOQ2357129
Authors: Yanyan Li 
Publication date: 19 June 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2017.04.025
Recommendations
- The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
- Independent sets in the graphs with bounded minors of the extended incidence matrix
- scientific article; zbMATH DE number 468640
- Independent domination in finitely defined classes of graphs
- Maximum independent sets in graphs of low degree
dominating set problemefficient algorithmindependent set problemmatrix minorBoolean linear programming
Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
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
- Mangoes and blueberries
- Toeplitz and circulant matrices: a review.
- Title not available (Why is that?)
- 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
Cited In (10)
- The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
- The complexity of some graph problems with bounded minors of their constraint matrices
- An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
- FPT-algorithms for some problems related to integer programming
- The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
- On lattice point counting in \(\varDelta\)-modular polyhedra
- Parameterized complexity of three edge contraction problems with degree constraints
- 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
- Independent sets in the graphs with bounded minors of the extended incidence matrix
This page was built for publication: The computational complexity of three graph 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 Q2357129)
