Alternating cycle-free matchings

DOI10.1007/BF00383169zbMath0805.68091MaRDI QIDQ1325959

Haiko Müller

Publication date: 15 May 1994

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

NP-completenesscomparability graphpartially ordered setsdistance hereditary graphschordal bipartite graphalternating cycle- free matchingsJump-numberP-solvability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Structural characterization of families of graphs (05C75)

Related Items (21)

Computing the jump number on semi-orders is polynomial ⋮ The bipartite margin shop and maximum red matchings free of blue-red alternating cycles ⋮ On unicyclic graphs with uniquely restricted maximum matchings ⋮ Unnamed Item ⋮ On edge perfectness and classes of bipartite graphs ⋮ Positive matching decompositions of graphs ⋮ The difficulty of beating the Taxman ⋮ On minimally non-firm binary matrices ⋮ Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Jump Number of Two-Directional Orthogonal Ray Graphs ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Flip distances between graph orientations ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Connected matchings in chordal bipartite graphs ⋮ Unicycle graphs and uniquely restricted maximum matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• Characterizations of strongly chordal graphs
• Distance-hereditary graphs
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Optimizing weakly triangulated graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Optimal Linear Extensions by Interchanging Chains
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• The Jump Number of Dags and Posets: An Introduction
• Minimizing Setups for Cycle-Free Ordered Sets
• Perfect matchings in hexagonal systems

This page was built for publication: Alternating cycle-free matchings