Star covers and star partitions of cographs and butterfly-free graphs
From MaRDI portal
Publication:6547835
DOI10.1007/978-3-031-52213-0_16MaRDI QIDQ6547835FDOQ6547835
Authors: J. Mondal, Sethu Vijayakumar 
Publication date: 31 May 2024
approximation algorithmscographspolynomial time algorithmsstar coverstar partitionbutterfly-free graphs
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68Wxx)
Cites Work
- Fundamentals of parameterized complexity
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Optimal packing of induced stars in a graph
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Independent set in \(P_5\)-free graphs in polynomial time
- On the completeness of a generalized matching problem
- Node-Deletion Problems on Bipartite Graphs
- Domination in convex and chordal bipartite graphs
- Set partitioning via inclusion-exclusion
- A linear algorithm for the domination number of a tree
- A Linear Recognition Algorithm for Cographs
- The path partition problem and related problems in bipartite graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- On graphs with polynomially solvable maximum-weight clique problem
- Title not available (Why is that?)
- Domination in permutation graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
- Star partitions on graphs
- Induced star partition of graphs
- Star covers and star partitions of double-split graphs
- On star partition of split graphs
Cited In (2)
This page was built for publication: Star covers and star partitions of cographs and butterfly-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6547835)
