Faster graph bipartization

DOI10.1016/j.jcss.2019.11.001zbMath1435.68241OpenAlexW2992705078WikidataQ126638101 ScholiaQ126638101MaRDI QIDQ2301359

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

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

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

Related Items (1)

Graph Bipartization Problem with Applications to Via Minimization in VLSI Design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Backdoors to q-Horn
• The complexity of König subgraph problems and above-guarantee vertex cover
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Almost 2-SAT is fixed-parameter tractable
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Parameterized complexity of finding subgraphs with hereditary properties.
• Maximum skew-symmetric flows and matchings
• Planar graph bipartization in linear time
• Path problems in skew-symmetric graphs
• Half-integrality, LP-branching, and FPT Algorithms
• Parameterized Approximations via d-Skew-Symmetric Multicut
• Maximal Flow Through a Network
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Graph Bipartization and via minimization
• Efficiency of a Good But Not Linear Set Union Algorithm
• Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
• Edge Bipartization Faster Than 2^k
• Multiway cuts in node weighted graphs
• Faster Parameterized Algorithms Using Linear Programming
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Antisymmetrical Digraphs

This page was built for publication: Faster graph bipartization