Independent packings in structured graphs

DOI10.1007/s10107-005-0649-5zbMath1078.05067OpenAlexW2061237693MaRDI QIDQ2583122

Kathie Cameron, Pavol Hell

Publication date: 13 January 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0649-5

zbMATH Keywords

Independent setCircular-arc graphChordal graphIntersection graphAsteroidal triple-free graphCocomparability graphInduced matchingInterval-filament graphPolygon-circle graphChordal bipartite graphDissociation setWeakly chordal graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (34)

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ The maximum number of maximum dissociation sets in trees ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ On spectral extrema of graphs with given order and dissociation number ⋮ Packing $k$-Matchings and $k$-Critical Graphs ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ On the vertex \(k\)-path cover ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ Brambles and independent packings in chordal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Irredundancy in circular arc graphs
• Weakly triangulated graphs
• Packing \(r\)-cliques in weighted chordal graphs
• Recognizing graphs without asteroidal triples
• Induced matchings in bipartite graphs
• Packings by cliques and by finite families of graphs
• Packing subgraphs in a graph
• NP-completeness of some generalizations of the maximum matching problem
• Comparability graphs and intersection graphs
• Thresholds for classes of intersection graphs
• Optimal parallel algorithms on circular-arc graphs
• Efficient subgraphs packing
• Covering and coloring polygon-circle graphs
• Induced matchings in asteroidal triple-free graphs
• Maximum induced matchings of random cubic graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Finding a maximum induced matching in weakly chordal graphs
• Optimizing weakly triangulated graphs
• Partitioning chordal graphs into independent sets and cliques
• On maximum induced matchings in bipartite graphs
• Algorithms for weakly triangulated graphs
• New results on induced matchings
• The graphs with maximum induced matching and maximum matching the same size
• On the Complexity of General Graph Factor Problems
• Representation of a finite graph by a set of intervals on the real line
• Stability in circular arc graphs
• Node-Deletion Problems on Bipartite Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• Graph Classes: A Survey
• Independent Sets in Asteroidal Triple-Free Graphs
• Bipartite Domination and Simultaneous Matroid Covers
• Induced matchings in cubic graphs
• The k‐piece packing problem
• Transitiv orientierbare Graphen
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Characterization of Comparability Graphs and of Interval Graphs
• Parallel algorithms on circular-arc graphs
• The \(K_r\)-packing problem

This page was built for publication: Independent packings in structured graphs