Parameterized complexity of induced graph matching on claw-free graphs
DOI10.1007/S00453-014-9877-5zbMATH Open1306.05163OpenAlexW2148030608MaRDI QIDQ487013FDOQ487013
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Data structures (68P05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- On the Complexity of General Graph Factor Problems
- Parameterized complexity of finding regular induced subgraphs
- Claw-free graphs---a survey
- Efficient graph representations
- Claw-free graphs. VII. Quasi-line graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A Problem Kernelization for Graph Packing
- Color-coding
- Looking at the stars
- Claw-free graphs. V. Global structure
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the parameterized complexity of multiple-interval graph problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Faster fixed-parameter tractable algorithms for matching and packing problems
- 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
- Normal Helly circular-arc graphs and its subclasses
- Induced disjoint paths in AT-free graphs
- Claw-free graphs. IV: Decomposition theorem
- Algorithms – ESA 2005
- Divide-and-Color
- On the recognition of fuzzy circular interval graphs
- Claw-free graphs. III: Circular interval graphs
- Coloring quasi-line graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
- Claw-free graphs. VI: Colouring
- Domination When the Stars Are Out
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- 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
- Title not available (Why is that?)
- Dominating set is fixed parameter tractable in claw-free graphs
Cited In (13)
- Disconnected cuts in claw-free graphs
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Title not available (Why is that?)
- Correction to: ``A connection between sports and matroids: how many teams can we beat?
- On the parameterized complexity of the acyclic matching problem
- Declawing a graph: polyhedra and branch-and-cut algorithms
- Parameterized Complexity of Independent Set in H-Free Graphs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterized complexity of independent set in H-free graphs
- Polynomial kernelization for removing induced claws and diamonds
- Induced Disjoint Paths in Claw-Free Graphs
- Polynomial Kernelization for Removing Induced Claws and Diamonds
This page was built for publication: Parameterized complexity of induced graph matching on claw-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q487013)
