Parameterized complexity of induced graph matching on claw-free graphs
From MaRDI portal
Publication:487013
DOI10.1007/s00453-014-9877-5zbMath1306.05163OpenAlexW2148030608MaRDI QIDQ487013
Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9877-5
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Data structures (68P05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes, Unnamed Item, Polynomial kernelization for removing induced claws and diamonds, Disconnected cuts in claw-free graphs, On the parameterized complexity of the acyclic matching problem, Parameterized Complexity of Independent Set in H-Free Graphs., Correction to: ``A connection between sports and matroids: how many teams can we beat?, Induced Disjoint Paths in Claw-Free Graphs, Declawing a graph: polyhedra and branch-and-cut algorithms, Polynomial Kernelization for Removing Induced Claws and Diamonds, Parameterized complexity of independent set in H-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the recognition of fuzzy circular interval graphs
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- Claw-free graphs. VI: Colouring
- Dominating set is fixed parameter tractable in claw-free graphs
- Looking at the stars
- Claw-free graphs. III: Circular interval graphs
- Claw-free graphs. IV: Decomposition theorem
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Claw-free graphs. V. Global structure
- On the parameterized complexity of multiple-interval graph problems
- Parameterized complexity of finding regular induced subgraphs
- Claw-free graphs---a survey
- Efficient graph representations
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- 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
- Restricted circular-arc graphs and clique cycles
- Claw-free graphs. VII. Quasi-line graphs
- Normal Helly circular-arc graphs and its subclasses
- Induced disjoint paths in AT-free graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Claw-free graphs. I: Orientable prismatic graphs
- Claw-free graphs. II: Non-orientable prismatic graphs
- Independent packings in structured graphs
- Induced Disjoint Paths in Claw-Free Graphs
- Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
- Domination When the Stars Are Out
- On the Complexity of General Graph Factor Problems
- Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
- Coloring quasi-line graphs
- Divide-and-Color
- A Problem Kernelization for Graph Packing
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Color-coding
- Algorithms – ESA 2005
