Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
DOI10.1007/s00453-018-0412-yzbMath1400.68085arXiv1801.04472OpenAlexW2963667635MaRDI QIDQ1799219
Ali Dehghan, Mohammad-Reza Sadeghi, Arash Ahadi
Publication date: 18 October 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1801.04472
total perfect dominating setzero-sum flow1-in-degree decompositionnot-all-equal decompositionzero-sum vertex flow
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On strongly planar not-all-equal 3SAT
- Algorithmic complexity of proper labeling problems
- Parameterized complexity of generalized domination problems
- Relating edge-coverings to the classification of \(\mathbb Z^k_2\)-magic graphs
- Zero-sum flows of the linear lattice.
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- The complexity of the zero-sum 3-flows
- Zero-sum flows in regular graphs
- Group flow, complex flow, unit vector flow, and the \((2 + \epsilon)\)-flow conjecture
- Tree decomposition by eigenvectors
- On the eigenvalues of distance powers of circuits
- On certain eigenspaces of cographs
- Nowhere-zero 4-flow in almost Petersen-minor free graphs
- On zero-sum 6-flows of graphs
- Partitioning a graph into alliance free sets
- Nowhere-zero integral flows on a bidirected graph
- Algorithmic approach to the satisfactory graph partitioning problem
- On the kernels of the incidence matrices of graphs
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Nowhere-zero 4-flows and cycle double covers
- Maximum gap labelings of graphs
- Nowhere-zero 3-flows and \(Z_{3}\)-connectivity of a family of graphs
- Every 8-uniform 8-regular hypergraph is 2-colorable
- On zero-sum \({\mathbb{Z}_k}\)-magic labelings of 3-regular graphs
- Sudoku graphs are integral
- On the null-spaces of acyclic and unicyclic singular graphs
- Nowhere-zero 15-flow in 3-edge-connected bidirected graphs
- On simply structured kernel bases of unicyclic graphs
- The satisfactory partition problem
- On simply structured bases of tree kernels
- On the algorithmic complexity of zero-sum edge-coloring
- Zero-Sum Flow Numbers of Regular Graphs
- Nowhere-Zero Flows on Signed Complete and Complete Bipartite Graphs
- Constant Sum Flows in Regular Graphs
- Zero-Sum Flow Numbers of Triangular Grids
- Minimum-weight triangulation is NP-hard
- The Even Cycle Problem for Directed Graphs
- A sufficient condition for a matrix to be totally unimodular
- Approximating theDomatic Number
- Rees algebras of edge ideals
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
- Zero-Sum Flow Numbers of Hexagonal Grids
- The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
- More about singular line graphs of trees
- A Contribution to the Theory of Chromatic Polynomials
- Polychromatic colorings of plane graphs
- Hard tiling problems with simple tiles
This page was built for publication: Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
