On stable cutsets in claw-free graphs and planar graphs
From MaRDI portal
Publication:935842
DOI10.1016/j.jda.2007.04.001zbMath1154.05317OpenAlexW1970916146MaRDI QIDQ935842
Haiko Müller, Van Bang Le, Raffaele Mosca
Publication date: 8 August 2008
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2007.04.001
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Vertex partitioning problems on graphs with bounded tree width ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Algorithms Solving the Matching Cut Problem ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Algorithms solving the matching cut problem ⋮ Dominating induced matchings in graphs without a skew star ⋮ 3-consecutive edge coloring of a graph ⋮ Satisfactory graph partition, variants, and generalizations
Cites Work
- New applications of clique separator decomposition for the maximum weight stable set problem
- Decomposition by clique separators
- Rectilinear planar layouts and bipolar orientations of planar graphs
- An algorithm for finding clique cut-sets
- Coloring graphs with stable cutsets
- Algorithms on clique separable graphs
- Stable set bonding in perfect graphs and parity graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- On stable cutsets in line graphs
- On stable cutsets in graphs
- A note on fragile graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Recognizing decomposable graphs
- Networks immune to isolated line failures
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- List Partitions
- A Split&Push Approach to 3D Orthogonal Drawing
- Fragile graphs with small independent cuts
- Matching cutsets in graphs
- ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
- Graph-Theoretic Concepts in Computer Science
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
