Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems

DOI10.1007/11847250_22zbMath1154.68568OpenAlexW2128203754MaRDI QIDQ3499742

Leizhen Cai, Siu-On Chan, Siu Man Chan

Publication date: 3 June 2008

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11847250_22

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Randomized algorithms (68W20)

Related Items (46)

On the ordered list subgraph embedding problems ⋮ Envy-free allocations respecting social networks ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ Parameterized Graph Cleaning Problems ⋮ Parameterized complexity of directed spanner problems ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ The complexity of degree anonymization by graph contractions ⋮ Parameterized algorithms for graph partitioning problems ⋮ Parameterized complexity of secluded connectivity problems ⋮ Parameterized aspects of strong subgraph closure ⋮ Parameterized complexity of perfectly matched sets ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Cleaning interval graphs ⋮ Parameterized complexity of finding connected induced subgraphs ⋮ Segmenting Strings Homogeneously Via Trees ⋮ Parameterized random complexity ⋮ Parameterized complexity of even/odd subgraph problems ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Exact algorithms for problems related to the densest \(k\)-set problem ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ How hard is it to satisfy (almost) all roommates ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Graph editing to a given degree sequence ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Parameterized graph cleaning problems ⋮ Graph Editing to a Given Degree Sequence ⋮ Homogeneous string segmentation using trees and weighted independent sets ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ Finding large degree-anonymous subgraphs is hard ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Unnamed Item ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ Two edge-disjoint paths with length constraints ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ Editing to a graph of given degrees ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs

This page was built for publication: Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems