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

DOI10.1016/j.ipl.2007.05.014zbMath1183.05084OpenAlexW2071629762MaRDI QIDQ2379999

Saket Saurabh, Venkatesh Raman

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

graph algorithmsexact algorithmparameterized complexitymax-cutdirected feedback arc set

Mathematics Subject Classification ID

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

Related Items

Studies in Computational Aspects of Voting ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Fixed-Parameter Algorithms for Kemeny Scores ⋮ Complexity of maximum cut on interval graphs ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Partial Kernelization for Rank Aggregation: Theory and Experiments ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Parametrized complexity theory.
• Measure and conquer
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Expected Computation Time for Hamiltonian Path problem
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• 3-coloring in time
• Theoretical Computer Science
• Automata, Languages and Programming
• Automata, Languages and Programming
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation