Clique Cover and Graph Separation
From MaRDI portal
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
Cites work
- \textsc{Multicut} is FPT
- A 2-approximation algorithm for the directed multiway cut problem
- A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A new and improved algorithm for the 3-cut problem
- A new approach to the minimum cut problem
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- Algorithms for compact letter displays: comparison and evaluation
- Almost 2-SAT is fixed-parameter tractable
- An improved approximation algorithm of MULTIWAY CUT.
- An improved parameterized algorithm for the minimum node multiway cut problem
- Applications of edge coverings by cliques
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Bipartite structure of all complex networks
- Can visibility graphs be represented compactly?
- Competing provers yield improved Karp-Lipton collapse results
- Covering edges by cliques with regard to keyword conflicts and intersection graphs
- Cutting up is hard to do: the parameterised complexity of k-cut and related problems
- Data reduction and exact algorithms for clique cover
- Efficiently covering complex networks with cliques of similar vertices
- Finding odd cycle transversals.
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- FPT algorithms for path-transversal and cycle-transversal problems
- scientific article; zbMATH DE number 4134090 (Why is no real title available?)
- scientific article; zbMATH DE number 5485527 (Why is no real title available?)
- scientific article; zbMATH DE number 89406 (Why is no real title available?)
- scientific article; zbMATH DE number 3582190 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 2044920 (Why is no real title available?)
- scientific article; zbMATH DE number 2229025 (Why is no real title available?)
- Incompressibility through Colors and IDs
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization -- preprocessing with a guarantee
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Kernelization Lower Bounds by Cross-Composition
- Kernelization: new upper and lower bound techniques
- Linear time algorithms on circular-arc graphs
- Multiway cuts in node weighted graphs
- On problems without polynomial kernels
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On the hardness of approximating minimization problems
- Parameterized graph separation problems
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Simple and improved parameterized algorithms for multiterminal cuts
- Some consequences of non-uniform conditions on uniform classes
- The Complexity of Multiterminal Cuts
- The minimum k-way cut of bounded size is fixed-parameter tractable
Cited in
(13)- Calculating approximation guarantees for partial set cover of pairs
- On some FPT problems without polynomial Turing compressions
- Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
- Clique cover and graph separation: new incompressibility results
- Pairs Covered by a Sequence of Sets
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Fractals for kernelization lower bounds
- On the kernel size of clique cover reductions for random intersection graphs
- Quick separation in chordal and split graphs
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Approximate Turing kernelization for problems parameterized by treewidth
- Exploiting dense structures in parameterized complexity
- Designing compact ILPs via fast witness verification
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)
