Star covers and star partitions of cographs and butterfly-free graphs
From MaRDI portal
Publication:6547835
DOI10.1007/978-3-031-52213-0_16MaRDI QIDQ6547835
Sethu Vijayakumar, Joyashree Mondal
Publication date: 31 May 2024
cographsapproximation algorithmspolynomial time algorithmsstar coverstar partitionbutterfly-free graphs
Algorithms in computer science (68Wxx) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
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
- Star partitions on graphs
- Induced star partition of graphs
- The path partition problem and related problems in bipartite graphs
- Set Partitioning via Inclusion-Exclusion
- A Linear Recognition Algorithm for Cographs
- Domination in permutation graphs
- On graphs with polynomially solvable maximum-weight clique problem
- Node-Deletion Problems on Bipartite Graphs
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- Star Partitions of Perfect Graphs
- Independent Set in P5-Free Graphs in Polynomial Time
- On the completeness of a generalized matching problem
- Star covers and star partitions of double-split graphs
- On star partition of split graphs
Related Items (2)
On star partition of split graphs ⋮ Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture
This page was built for publication: Star covers and star partitions of cographs and butterfly-free graphs
