Minimum partition of an independence system into independent sets

DOI10.1016/j.disopt.2008.10.001zbMath1160.90682OpenAlexW1978182645MaRDI QIDQ1013303

Sanming Zhou

Publication date: 17 April 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2008.10.001

zbMATH Keywords

split graphdomination numberhereditary propertyconnected domination numberclique domination numberconditional chromatic numberconditional colouringminimum set cover problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Minimum partition of an \(r\)-independence system, Solving Graph Partitioning Problems with Parallel Metaheuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• Greedoids
• Estimations for the domination number of a graph
• Boolean techniques for matroidal decomposition of independence systems and applications to graphs
• A generalization of antiwebs to independence systems and their canonical facets
• The greedy algorithm for partially ordered sets
• An interpolation theorem for partitions which are indivisible with respect to cohereditary properties
• Graph properties and hypergraph colourings
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Chromatic partitions of a graph
• Domination number and neighbourhood conditions
• A sequential coloring algorithm for finite sets
• Hereditary systems and greedy-type algorithms.
• Interpolation theorems for graphs, hypergraphs and matroids
• The subchromatic number of a graph
• On the geometric structure of independence systems
• An interpolation theorem for partitions which are complete with respect to hereditary properties
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On generalized graph colorings
• On the Facial Structure of Independence System Polyhedra
• A Greedy Heuristic for the Set-Covering Problem
• Worst case analysis of greedy type algorithms for independence systems
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Augmenting Paths and a Class of Independence Systems
• Closure in Independence Systems
• Coloring Theories
• K-greedy algorithms for independence systems
• On the Problem of a Generalization of the Hamilton-Jacobi Method for Nonholonomic Systems
• An Analysis of the Greedy Heuristic for Independence Systems
• On a certain class of polytopes associated with independence systems.
• Properties of vertex packing and independence system polyhedra
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Minimum partition of a matroid into independent subsets
• COVERING AND PACKING IN GRAPHS, I.
• Dominating cliques in graphs