Minimum partition of an independence system into independent sets

DOI10.1016/J.DISOPT.2008.10.001MaRDI QIDQ1013303zbMATH OpenOpenAlexFDO

Authors 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

clique domination numberconditional chromatic numberconditional colouringconnected domination numberdomination numberhereditary propertyminimum set cover problemsplit graph

Mathematics Subject Classification ID

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

Recommendations

• Minimum partition of an \(r\)-independence system
• scientific article; zbMATH DE number 404527
• Colored-independence (mostly) on trees
• On the number of maximal independent sets in minimum colorings of split graphs
• scientific article; zbMATH DE number 4010539

Cites work

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

Cited in

(4)

• Minimum partition of an \(r\)-independence system
• scientific article; zbMATH DE number 404527 (Why is no real title available?)
• Solving graph partitioning problems with parallel metaheuristics
• scientific article; zbMATH DE number 2230919 (Why is no real title available?)

This page was built for publication: Minimum partition of an independence system into independent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1013303)