Treewidth reduction for constrained separation and bipartization problems

DOI10.4230/LIPICS.STACS.2010.2485MaRDI QIDQ3113780zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Barry O'Sullivan, Igor Razgon

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_8571.html

zbMATH Keywords

fixed-parameter algorithmsgraph separation problemstreewidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Finding small separators in linear time via treewidth reduction
• Parameterized and Exact Computation
• Parameterized graph separation problems
• Sharp separation and applications to exact and parameterized algorithms
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability

Cited in

(13)

• Constrained domatic bipartition on trees
• An FPT algorithm for matching cut and d-cut
• Treewidth of graphs with balanced separations
• On polynomial kernels for structural parameterizations of odd cycle transversal
• Finding small separators in linear time via treewidth reduction
• Reducing Separable Convex Programs with Tree Constraints
• Sharp separation and applications to exact and parameterized algorithms
• On the parameterized complexity of finding separators with non-hereditary properties
• Near optimal seperation of tree-like and general resolution
• Parameterizing cut sets in a graph by the number of their components
• On parameterized independent feedback vertex set
• Cuts in graphs with matroid constraints
• Property testing in Gaussian graphical models: trees and small separation numbers

This page was built for publication: Treewidth reduction for constrained separation and bipartization problems

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