On maximal chain subgraphs and covers of bipartite graphs

DOI10.1007/978-3-319-44543-4_11MaRDI QIDQ2819498zbMATH OpenOpenAlexFDO

Authors Mattia Gastaldello, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri, Tiziana Calamoneri

Publication date 29 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01388546/file/PaperIWOCA2016.pdf

zbMATH Keywords

chain subgraph cover problemenumeration algorithmsexact exponential algorithms

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A min-max property of chordal bipartite graphs with applications
• On the complexity of the k-chain subgraph cover problem
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Efficient enumeration of bipartite subgraphs in graphs
• Approximating the Minimum Chain Completion problem

Cites work

• Algorithm Theory - SWAT 2004
• Generating bicliques of a graph in lexicographic order
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On cliques in graphs
• On generating all maximal independent sets
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of the k-chain subgraph cover problem
• On the generation of bicliques of a graph
• Set partitioning via inclusion-exclusion
• The Complexity of the Partial Order Dimension Problem
• The induced matching and chain subgraph cover problems for convex bipartite graphs

Cited in

(5)

• Efficient enumeration of bipartite subgraphs in graphs
• On the 2-Chain Subgraph Cover and Related Problems
• Maximal chains of isomorphic subgraphs of the Rado graph
• Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
• Approximating the Minimum Chain Completion problem

This page was built for publication: On maximal chain subgraphs and covers of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819498)