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

parameterized approximationodd cycle transversalimportant separatorsgraph bipartization

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• LP can be a cure for parameterized problems
• Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
• 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
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(12)

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

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)