Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
From MaRDI portal
Publication:2379999
DOI10.1016/J.IPL.2007.05.014zbMATH Open1183.05084OpenAlexW2071629762MaRDI QIDQ2379999FDOQ2379999
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
Cites Work
- Title not available (Why is that?)
- Parametrized complexity theory.
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- 3-coloring in time
- Title not available (Why is that?)
- Automata, Languages and Programming
- Algorithms and Computation
- Enumerating maximal independent sets with applications to graph colouring.
- Title not available (Why is that?)
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Title not available (Why is that?)
- Measure and conquer
- Expected Computation Time for Hamiltonian Path problem
- Title not available (Why is that?)
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Graph-Theoretic Concepts in Computer Science
- Theoretical Computer Science
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- Automata, Languages and Programming
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
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
- An Exact Method for the Minimum Feedback Arc Set Problem
- Linear kernels and linear-time algorithms for finding large cuts
- Partial kernelization for rank aggregation: theory and experiments
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Fixed-parameter algorithms for Kemeny rankings
- \((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
- Parameterized Complexity of Multi-Node Hubs
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)
