Distance-d independent set problems for bipartite and chordal graphs
DOI10.1007/S10878-012-9594-4zbMATH Open1302.68139OpenAlexW2071807296MaRDI QIDQ2436655FDOQ2436655
Fengrui Guo, Hiroshi Eto, Eiji Miyano
Publication date: 25 February 2014
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-012-9594-4
Recommendations
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
- Approximation algorithm for the distance-3 independent set problem on cubic graphs
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- Computing \(k\)-independent sets for regular bipartite graphs
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Title not available (Why is that?)
- Algorithms on circular-arc graphs
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- On maximal independent sets of vertices in claw-free graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The complexity of comparability graph recognition and coloring
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- On powers of chordal graphs and their colorings
- Title not available (Why is that?)
- Maximum weight independent sets in hole- and co-chair-free graphs
- Computing independent sets in graphs with large girth
- On powers of \(m\)-trapezoid graphs
- Distance-d Independent Set Problems for Bipartite and Chordal Graphs
- Title not available (Why is that?)
- Powers of geometric intersection graphs and dispersion algorithms
- On powers of circular arc graphs and proper circular arc graphs
Cited In (14)
- The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
- Vertex cover at distance on \(H\)-free graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- A new approach on locally checkable problems
- On the computational complexity of the Helly number in the \(P_3\) and related convexities
- Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
- Packing 2- and 3-stars into cubic graphs
- Structurally parameterized \(d\)-scattered set
- Packing 2- and 3-stars into \(( 2 , 3 )\)-regular graphs
- Improved (In-)Approximability Bounds for d-Scattered Set
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
This page was built for publication: Distance-\(d\) independent set problems for bipartite and chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436655)
