Induced matchings
From MaRDI portal
Publication:1262877
DOI10.1016/0166-218X(92)90275-FzbMath0687.05033WikidataQ61920235 ScholiaQ61920235MaRDI QIDQ1262877
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
Augmenting approach for some maximum set problems ⋮ A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ The complexity of induced minors and related problems ⋮ Complexity aspects of generalized Helly hypergraphs ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ On graphs with induced matching number almost equal to matching number ⋮ Induced matching extendable graph powers ⋮ Unnamed Item ⋮ Maximum induced matchings in graphs ⋮ Graphs with maximal induced matchings of the same size ⋮ Graph matching problems and the NP-hardness of sortedness constraints ⋮ A characterization of well-indumatchable graphs having girth greater than seven ⋮ Exact algorithms for maximum induced matching ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ Maximum matching in multi-interface networks ⋮ Induced matchings in subcubic graphs without short cycles ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Matchings, coverings, and Castelnuovo-Mumford regularity ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Strong edge-coloring for cubic Halin graphs ⋮ Strong edge chromatic index of the generalized Petersen graphs ⋮ The strong chromatic index of Halin graphs ⋮ Maximum Induced Matchings in Grids ⋮ Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ Maximum \(k\)-regular induced subgraphs ⋮ On the strong chromatic index of cubic Halin graphs ⋮ Characterization of the induced matching extendable graphs with \(2 n\) vertices and \(3 n\) edges ⋮ Degenerate matchings and edge colorings ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Induced matchings in asteroidal triple-free graphs ⋮ A note on characterization of the induced matching extendable Cayley graphs generated by transpositions ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Strong edge-colouring and induced matchings ⋮ Unnamed Item ⋮ Induced matchings in intersection graphs. ⋮ New results on induced matchings ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Degree conditions of induced matching extendable graphs ⋮ Two greedy consequences for maximum induced matchings ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Complexity of simplicial homology and independence complexes of chordal graphs ⋮ Maximum cardinality neighbourly sets in quadrilateral free graphs ⋮ On complexity of special maximum matchings constructing ⋮ On chordal graph and line graph squares ⋮ Approximating weighted induced matchings ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ On the strong \(p\)-Helly property ⋮ On the approximability of the maximum induced matching problem ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Generalized subgraph-restricted matchings in graphs ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Partition a graph with small diameter into two induced matchings ⋮ 4-regular claw-free IM-extendable graphs ⋮ Number of induced matchings of graphs ⋮ The induced separation dimension of a graph ⋮ Maximum induced matching of hexagonal graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ New kernels for several problems on planar graphs ⋮ Bipartite matching extendable graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Strong edge-coloring for jellyfish graphs ⋮ Equality of distance packing numbers ⋮ Efficient edge domination in regular graphs ⋮ Proof of a conjecture on the strong chromatic index of Halin graphs ⋮ Induced disjoint paths in AT-free graphs ⋮ The Private Neighbor Concept ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ Induced Matchings in Graphs of Bounded Maximum Degree ⋮ The parameterized complexity of the induced matching problem ⋮ Some results on graphs without long induced paths ⋮ Induced packing of odd cycles in planar graphs ⋮ Maximum induced matching problem on hhd-free graphs ⋮ Dominating Induced Matchings ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ The \(\text{v} \)-number of monomial ideals ⋮ Edge-deletable IM-extendable graphs with minimum number of edges ⋮ Brambles and independent packings in chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ On maximum induced matchings in bipartite graphs ⋮ A generalization of extension complexity that captures P ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ Maximum induced matchings close to maximum matchings ⋮ On the computational complexity of strong edge coloring ⋮ Moderately exponential time algorithms for the maximum induced matching problem ⋮ Some results on dominating induced matchings ⋮ Packing \(r\)-cliques in weighted chordal graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs ⋮ Maximum induced matchings of random cubic graphs
Cites Work
- On rigid circuit graphs
- Characterizations of strongly chordal graphs
- A characterisation of rigid circuit graphs
- Incidence matrices and interval graphs
- Normal hypergraphs and the perfect graph conjecture
- 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
- Totally-Balanced and Greedy Matrices
- Representations of chordal graphs as subtrees of a tree
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Induced matchings
