The computational complexity of three graph problems for instances with bounded minors of constraint matrices

DOI10.1016/J.DAM.2017.04.025MaRDI QIDQ2357129zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dominating set problemefficient algorithmindependent set problemmatrix minorBoolean linear programming

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• 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
• 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
• Mangoes and blueberries
• On linear and circular structure of (claw, net)-free graphs
• Polynomial algorithms in linear programming
• Toeplitz and circulant matrices: a review.

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)