Clique Cover and Graph Separation
From MaRDI portal
Publication:2943572
DOI10.1145/2594439zbMATH Open1321.68302OpenAlexW1992349235MaRDI QIDQ2943572FDOQ2943572
Authors: Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström 
Publication date: 3 September 2015
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2594439
Recommendations
- Clique cover and graph separation: new incompressibility results
- On clique coverings of complete multipartite graphs
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- The complexity of generalized clique covering
- Clique partitions, graph compression and speeding-up algorithms
- Clique covering of graphs
- An improved upper bound and algorithm for clique covers
- Compressed cliques graphs, clique coverings and positive zero forcing
- scientific article; zbMATH DE number 68359
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- Finding odd cycle transversals.
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Kernelization -- preprocessing with a guarantee
- Subset feedback vertex set is fixed-parameter tractable
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Incompressibility through Colors and IDs
- The Complexity of Multiterminal Cuts
- FPT algorithms for path-transversal and cycle-transversal problems
- Multiway cuts in node weighted graphs
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Parameterized graph separation problems
- Title not available (Why is that?)
- Kernelization Lower Bounds by Cross-Composition
- Infeasibility of instance compression and succinct PCPs for NP
- Can visibility graphs be represented compactly?
- On the hardness of approximating minimization problems
- Title not available (Why is that?)
- An improved parameterized algorithm for the minimum node multiway cut problem
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- \textsc{Multicut} is FPT
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- Fixed-parameter tractability of multicut in directed acyclic graphs
- Kernel bounds for disjoint cycles and disjoint paths
- Some consequences of non-uniform conditions on uniform classes
- Simple and improved parameterized algorithms for multiterminal cuts
- Competing provers yield improved Karp-Lipton collapse results
- A new approach to the minimum cut problem
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Linear time algorithms on circular-arc graphs
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Kernelization: new upper and lower bound techniques
- A new and improved algorithm for the 3-cut problem
- Applications of edge coverings by cliques
- Title not available (Why is that?)
- Data reduction and exact algorithms for clique cover
- An improved approximation algorithm of MULTIWAY CUT.
- Algorithms for compact letter displays: comparison and evaluation
- Efficiently covering complex networks with cliques of similar vertices
- Bipartite structure of all complex networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Covering edges by cliques with regard to keyword conflicts and intersection graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
- A 2-approximation algorithm for the directed multiway cut problem
Cited In (11)
- Quick separation in chordal and split graphs
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Known Algorithms for Edge Clique Cover are Probably Optimal
- Clique cover and graph separation: new incompressibility results
- Calculating approximation guarantees for partial set cover of pairs
- On the kernel size of clique cover reductions for random intersection graphs
- Fractals for kernelization lower bounds
- On some FPT problems without polynomial Turing compressions
- Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
- Pairs Covered by a Sequence of Sets
This page was built for publication: Clique Cover and Graph Separation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943572)
