Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG

DOI10.1016/J.IPL.2007.05.014MaRDI QIDQ2379999zbMATH OpenOpenAlexFDO

Authors Venkatesh Raman, Saket Saurabh

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.05.014

zbMATH Keywords

exact algorithmgraph algorithmsparameterized complexitymax-cutdirected feedback arc set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• scientific article; zbMATH DE number 5605070 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• 3-coloring in time
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Algorithms and Computation
• Automata, Languages and Programming
• Automata, Languages and Programming
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Enumerating maximal independent sets with applications to graph colouring.
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Expected Computation Time for Hamiltonian Path problem
• Graph-Theoretic Concepts in Computer Science
• Measure and conquer
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parametrized complexity theory.
• Theoretical Computer Science
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(13)

• Studies in Computational Aspects of Voting
• Computing the largest bond and the maximum connected cut of a graph
• Complexity of maximum cut on interval graphs
• Linear kernels and linear-time algorithms for finding large cuts
• Partial kernelization for rank aggregation: theory and experiments
• Parameterized complexity of multi-node hubs
• Fixed-parameter algorithms for Kemeny rankings
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• An exact method for the minimum feedback arc set problem
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Parameterized complexity of multi-node hubs
• Fixed-Parameter Algorithms for Kemeny Scores

This page was built for publication: Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG

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