Faster graph bipartization

DOI10.1016/J.JCSS.2019.11.001MaRDI QIDQ2301359zbMATH OpenOpenAlexWikidataFDO

Authors Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh

Publication date 24 February 2020

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2019.11.001

zbMATH Keywords

graph bipartizationimportant separatorsodd cycle transversalparameterized approximation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Edge Bipartization Faster Than 2ᵏ
• Edge bipartization faster than \(2^k\)
• Planar graph bipartization in linear time
• scientific article; zbMATH DE number 6297714
• Algorithm Engineering for Optimal Graph Bipartization

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Almost 2-SAT is fixed-parameter tractable
• Antisymmetrical Digraphs
• Backdoors to q-Horn
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Edge Bipartization Faster Than 2ᵏ
• Efficiency of a Good But Not Linear Set Union Algorithm
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Graph Bipartization and via minimization
• Half-integrality, LP-branching, and FPT algorithms
• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 1945152 (Why is no real title available?)
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)
• Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
• LP can be a cure for parameterized problems
• Maximal Flow Through a Network
• Maximum skew-symmetric flows and matchings
• Multiway cuts in node weighted graphs
• Parameterized approximations via d-skew-symmetric multicut
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized graph separation problems
• Path problems in skew-symmetric graphs
• Planar graph bipartization in linear time
• Subexponential parameterized odd cycle transversal on planar graphs
• The complexity of König subgraph problems and above-guarantee vertex cover

Cited in

(13)

• Fast diameter computation within split graphs
• Planar graph bipartization in linear time
• On polynomial kernels for structural parameterizations of odd cycle transversal
• Very cost effective bipartitions in graphs
• Edge Bipartization Faster Than 2ᵏ
• Strong parameterized deletion: bipartite graphs
• An Updated Experimental Evaluation of Graph Bipartization Methods
• Parameterized algorithms for even cycle transversal
• Linear time parameterized algorithms via skew-symmetric multicuts
• Graph Bipartization Problem with Applications to Via Minimization in VLSI Design
• Edge bipartization faster than \(2^k\)
• Odd cycle transversal on P₅-free graphs in polynomial time
• Quasipolynomial-time deterministic kernelization and (gammoid) representation

This page was built for publication: Faster graph bipartization

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