What makes equitable connected partition easy

DOI10.1007/978-3-642-11269-0_10MaRDI QIDQ3656856zbMATH OpenOpenAlexWikidataFDO

Authors Rosa I. Enciso, Michael R. Fellows, Jiong Guo, Frances Rosamond, Ondřej Suchý, Iyad Kanj

Publication date 14 January 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11269-0_10

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 7058467
• Mathematical Foundations of Computer Science 2004
• Equitable colorings of bounded treewidth graphs
• Tree-coloring problems of bounded treewidth graphs
• Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Cited in

(20)

• Structural parameterizations for equitable coloring
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• On the parameterized complexity of computing balanced partitions in graphs
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• Iterated Type Partitions
• Grundy Distinguishes Treewidth from Pathwidth
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Grundy distinguishes treewidth from pathwidth
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• Extended MSO model checking via small vertex integrity
• Destroying densest subgraphs is hard
• Destroying densest subgraphs is hard
• Finding vertex-surjective graph homomorphisms
• Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
• The parameterised complexity of computing the maximum modularity of a graph

This page was built for publication: What makes equitable connected partition easy

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