On the computational complexity of upper fractional domination
From MaRDI portal
Publication:753848
DOI10.1016/0166-218X(90)90065-KzbMath0717.05068MaRDI QIDQ753848
D. Pokrass Jacobs, Stephen T. Hedetniemi, Grant A. Cheston, Gerd H. Fricke
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph theory (05C99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (27)
Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance ⋮ The determinant of a tree's neighborhood matrix ⋮ CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY ⋮ Maximal irredundant functions ⋮ A maximum dicut in a digraph induced by a minimal dominating set ⋮ Weighted upper domination number ⋮ THE MINIMAL DOMINATING SETS IN A DIRECTED GRAPH AND THE KEY INDICATORS SET OF SOCIO–ECONOMIC SYSTEM ⋮ The many facets of upper domination ⋮ On the computational complexity of upper total domination ⋮ In)approximability of Maximum Minimal FVS ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ A constraint generation algorithm for large scale linear programs using multiple-points separation ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Algorithmic aspects of upper edge domination ⋮ (In)approximability of maximum minimal FVS ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ The Private Neighbor Concept ⋮ Fractional Dominating Parameters ⋮ A Boundary Property for Upper Domination ⋮ Upper Domination: Complexity and Approximation ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ The b-chromatic number of a graph ⋮ Linear programming approach for various domination parameters ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Complexity of the max cut problem with the minimal domination constraint
Cites Work
- Domination, independent domination, and duality in strongly chordal graphs
- Fractional matchings and the Edmonds-Gallai theorem
- Fractional matchings and covers in infinite hypergraphs
- Contributions to the theory of domination, independence and irredundance in graphs
- Linear algorithms on recursive representations of trees
- Solving covering problems and the uncapacitated plant location problem on trees
- Packing Problems and Hypergraph Theory: A Survey
- On the Fractional Covering Number of Hypergraphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the computational complexity of upper fractional domination
