Algorithm Engineering for Optimal Graph Bipartization

DOI10.7155/JGAA.00177MaRDI QIDQ3627967zbMATH OpenOpenAlexFDO

Authors Falk Hüffner

Publication date 19 May 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://eudml.org/doc/45460

zbMATH Keywords

iterative compression method

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Experimental and Efficient Algorithms
• Engineering multilevel graph partitioning algorithms
• scientific article; zbMATH DE number 5761786
• Algorithmic aspects of bipartite graphs
• Graph Bipartization and via minimization
• Efficient algorithms for a graph partitioning problem
• A linear algorithm for bipartition of biconnected graphs
• An algorithm for improving graph partitions
• scientific article; zbMATH DE number 7651215

Cited in

(24)

• Odd cycle transversal on P₅-free graphs in polynomial time
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• Graph Bipartization and via minimization
• On polynomial kernels for structural parameterizations of odd cycle transversal
• An Updated Experimental Evaluation of Graph Bipartization Methods
• The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
• Resilience and optimization of identifiable bipartite graphs
• Theoretical Computer Science
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• On bipartization of cubic graphs by removal of an independent set
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• scientific article; zbMATH DE number 4150228 (Why is no real title available?)
• Experimental and Efficient Algorithms
• Preprocessing to reduce the search space for odd cycle transversal
• Another disjoint compression algorithm for odd cycle transversal
• Planar graph bipartization in linear time
• scientific article; zbMATH DE number 4135976 (Why is no real title available?)
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Edge bipartization faster than \(2^k\)
• Hitting selected (odd) cycles
• Fixed-parameter algorithms in analysis of heuristics for extracting networks in linear programs
• Faster graph bipartization
• Experimental and Efficient Algorithms

This page was built for publication: Algorithm Engineering for Optimal Graph Bipartization

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