Induced star partition of graphs

DOI10.1016/j.dam.2021.04.015zbMath1494.05093OpenAlexW3159723557MaRDI QIDQ2161236

Yanyan Li

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.04.015

zbMATH Keywords

NP-completenessapproximation algorithmspolynomial time algorithmsexact algorithmsFPTinduced star partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (1)

Star covers and star partitions of double-split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Domination in convex and chordal bipartite graphs
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• A linear algorithm for the domination number of a tree
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Optimal packing of induced stars in a graph
• Geometric versions of the three-dimensional assignment problem under general norms
• Partition the vertices of a graph into induced matchings
• The path partition problem and related problems in bipartite graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Set Partitioning via Inclusion-Exclusion
• Domination in permutation graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Star Partitions of Perfect Graphs
• On the completeness of a generalized matching problem
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Induced star partition of graphs