On the computational complexity of upper fractional domination
From MaRDI portal
DOI10.1016/0166-218X(90)90065-KzbMATH Open0717.05068MaRDI QIDQ753848FDOQ753848
Authors: Grant A. Cheston, Stephen T. Hedetniemi, D. P. Jacobs, Gerd H. Fricke 
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
Extremal problems in graph theory (05C35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (05C99)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Domination, independent domination, and duality in strongly chordal graphs
- Solving covering problems and the uncapacitated plant location problem on trees
- Linear algorithms on recursive representations of trees
- Title not available (Why is that?)
- Contributions to the theory of domination, independence and irredundance in graphs
- Fractional matchings and the Edmonds-Gallai theorem
- Packing Problems and Hypergraph Theory: A Survey
- Title not available (Why is that?)
- Fractional matchings and covers in infinite hypergraphs
- Title not available (Why is that?)
- On the Fractional Covering Number of Hypergraphs
- Title not available (Why is that?)
Cited In (31)
- Title not available (Why is that?)
- A maximum dicut in a digraph induced by a minimal dominating set
- Vector representation of graph domination
- CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY
- Bibliography on domination in graphs and some basic definitions of domination parameters
- On the computational complexity of upper total domination
- Upper domination: towards a dichotomy through boundary properties
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- In)approximability of Maximum Minimal FVS
- The private neighbor concept
- Fractional dominating parameters
- The b-chromatic number of a graph
- Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
- Algorithmic aspects of upper edge domination
- Maximal irredundant functions
- A boundary property for upper domination
- Upper domination: complexity and approximation
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Linear programming approach for various domination parameters
- THE MINIMAL DOMINATING SETS IN A DIRECTED GRAPH AND THE KEY INDICATORS SET OF SOCIO–ECONOMIC SYSTEM
- The determinant of a tree's neighborhood matrix
- (In)approximability of maximum minimal FVS
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Unsolved algorithmic problems on trees
- Weighted upper domination number
- The many facets of upper domination
- A constraint generation algorithm for large scale linear programs using multiple-points separation
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
- Complexity of the max cut problem with the minimal domination constraint
- Title not available (Why is that?)
This page was built for publication: On the computational complexity of upper fractional domination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753848)
