On the k-edge-incident subgraph problem and its variants

DOI10.1016/J.DAM.2013.06.014MaRDI QIDQ2446891zbMATH OpenOpenAlexFDO

Authors Hongyu Liang

Publication date 23 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.06.014

zbMATH Keywords

\(k\)-edge-incident subgraph problemapproximation algorithmdense graphminimum partial vertex cover problempolynomial-time approximation scheme

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Approximation algorithms (68W25)

Recommendations

• \(k\)-edge subgraph problems
• The parameterized complexity of k-edge induced subgraphs
• The Parameterized Complexity of k-Edge Induced Subgraphs
• A result about the incident edges in the graphs \(M_ k\)
• On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• The k-node connected subgraph problem: polyhedral analysis and branch-and-cut
• On the complexity of some subgraph problems
• The dense \(k\)-subgraph problem

Cites work

• \(k\)-edge subgraph problems
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• A threshold of ln n for approximating set cover
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• Densest k-subgraph approximation on intersection graphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Dial a ride from k-forest
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Improved approximation bounds for edge dominating set in dense graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Parameterized complexity of Vertex Cover variants
• Parametrized complexity theory.
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• PTAS for Densest k-Subgraph in Interval Graphs
• The densest \(k\)-subgraph problem on clique graphs
• The design of approximation algorithms
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema

Cited in

(3)

• \(k\)-edge subgraph problems
• On set expansion problems and the small set expansion conjecture
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition

This page was built for publication: On the \(k\)-edge-incident subgraph problem and its variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446891)