Induced matchings
From MaRDI portal
DOI10.1016/0166-218X(92)90275-FzbMATH Open0687.05033WikidataQ61920235 ScholiaQ61920235MaRDI QIDQ1262877FDOQ1262877
Authors: Kathie Cameron 
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Normal hypergraphs and the perfect graph conjecture
- Title not available (Why is that?)
- Incidence matrices and interval graphs
- Title not available (Why is that?)
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- Representations of chordal graphs as subtrees of a tree
- Characterizations of strongly chordal graphs
- Title not available (Why is that?)
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Totally-Balanced and Greedy Matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- A characterisation of rigid circuit graphs
Cited In (only showing first 100 items - show all)
- Maximum matching in multi-interface networks
- Induced matchings in subcubic graphs without short cycles
- On the strong \(p\)-Helly property
- The graphs with maximum induced matching and maximum matching the same size
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Matchings, coverings, and Castelnuovo-Mumford regularity
- On the strong chromatic index of cubic Halin graphs
- Induced matchings in graphs of bounded maximum degree
- Induced Matching in Some Subclasses of Bipartite Graphs
- Strong edge-coloring for cubic Halin graphs
- On the sequentially Cohen-Macaulay properties of almost complete multipartite graphs
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Approximating weighted induced matchings
- Augmenting approach for some maximum set problems
- Complexity aspects of generalized Helly hypergraphs
- Almost induced matching: linear kernels and parameterized algorithms
- Maximum induced matchings of random cubic graphs
- The complexity of dissociation set problems in graphs
- On the Induced Matching Problem
- Generalized subgraph-restricted matchings in graphs
- Parameterized algorithms and kernels for almost induced matching
- The induced separation dimension of a graph
- Maximum induced matching of hexagonal graphs
- Maximum induced matching problem on hhd-free graphs
- A generalization of extension complexity that captures P
- Editing graphs to satisfy degree constraints: a parameterized approach
- On the computational complexity of strong edge coloring
- Exact algorithms for maximum induced matching
- Some results on graphs without long induced paths
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
- Maximum weight induced matching in some subclasses of bipartite graphs
- A min-max property of chordal bipartite graphs with applications
- Proof of a conjecture on the strong chromatic index of Halin graphs
- The strong chromatic index of Halin graphs
- Induced packing of odd cycles in planar graphs
- On graphs with induced matching number almost equal to matching number
- Graphs with maximal induced matchings of the same size
- On induced matchings
- On maximum induced matchings in bipartite graphs
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Induced matchings in intersection graphs
- Maximum \(k\)-regular induced subgraphs
- Induced matchings in asteroidal triple-free graphs
- Efficient edge domination in regular graphs
- The parameterized complexity of the induced matching problem
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- On distance-3 matchings and induced matchings
- Dominating induced matchings
- Maximum induced matchings in graphs
- A note on the NP-hardness of two matching problems in induced subgrids
- Approximability results for the maximum and minimum maximal induced matching problems
- Two greedy consequences for maximum induced matchings
- Maximum induced matchings for chordal graphs in linear time
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- Large Induced Subgraphs via Triangulations and CMSO
- 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
- New results on maximum induced matchings in bipartite graphs and beyond
- Maximum cardinality neighbourly sets in quadrilateral free graphs
- The complexity of induced minors and related problems
- Number of induced matchings of graphs
- On the approximability of the maximum induced matching problem
- Induced matchings in intersection graphs.
- On the induced matching problem in Hamiltonian bipartite graphs
- New results on induced matchings
- On complexity of special maximum matchings constructing
- On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
- Packing \(r\)-cliques in weighted chordal graphs
- Finding a maximum induced matching in weakly chordal graphs
- Complexity of simplicial homology and independence complexes of chordal graphs
- Maximum induced matchings close to maximum matchings
- Strong edge-colouring and induced matchings
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
- Treewidth versus clique number. II: Tree-independence number
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- A bisection approach to subcubic maximum induced matching
- Exact Solution Algorithms for the Chordless Cycle Problem
- Induced forests in some distance-regular graphs
- Some results on dominating induced matchings
- Connected matchings in chordal bipartite graphs
- The conditions of a matching being induced
- A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
- Induced matching extendable graph powers
- Graph matching problems and the NP-hardness of sortedness constraints
- Induced matchings in graphs of degree at most 4
- Bipartite matching extendable graphs
- Degenerate matchings and edge colorings
- On some hard and some tractable cases of the maximum acyclic matching problem
- The private neighbor concept
- MIP formulations for induced graph optimization problems: a tutorial
- Hardness of computing width parameters based on branch decompositions over the vertex set
- On the parameterized complexity of the acyclic matching problem
- Weighted connected matchings
- On the complexity of minimum maximal acyclic matchings
- On the hardness of deciding the equality of the induced and the uniquely restricted matching number
- Generalizing the induced matching by edge capacity constraints
- Degree conditions of induced matching extendable graphs
- Acyclic matchings
This page was built for publication: Induced matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262877)
