Distance-d independent set problems for bipartite and chordal graphs

DOI10.1007/S10878-012-9594-4MaRDI QIDQ2436655zbMATH OpenOpenAlexFDO

Authors Hiroshi Eto, Fengrui Guo, 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

zbMATH Keywords

computational complexitychordal graphsbipartite graphsdistance-\(d\) independent set

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3834023 (Why is no real title available?)
• scientific article; zbMATH DE number 4045800 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Algorithms on circular-arc graphs
• Computing independent sets in graphs with large girth
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph Classes: A Survey
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum weight independent sets in hole- and co-chair-free graphs
• On maximal independent sets of vertices in claw-free graphs
• On powers of \(m\)-trapezoid graphs
• On powers of chordal graphs and their colorings
• On powers of circular arc graphs and proper circular arc graphs
• Powers of geometric intersection graphs and dispersion algorithms
• Some simplified NP-complete graph problems
• The complexity of comparability graph recognition and coloring

Cited in

(15)

• Packing 2- and 3-stars into \(( 2 , 3 )\)-regular graphs
• Vertex cover at distance on \(H\)-free graphs
• Packing 2- and 3-stars into cubic graphs
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• Approximation algorithm for the distance-3 independent set problem on cubic graphs
• Improved (In-)Approximability Bounds for d-Scattered Set
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• A new approach on locally checkable problems
• On the computational complexity of the Helly number in the \(P_3\) and related convexities
• Structurally parameterized \(d\)-scattered set
• On the complexity of distance-\(d\) independent set reconfiguration

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)