On Maximal Chain Subgraphs and Covers of Bipartite Graphs

DOI10.1007/978-3-319-44543-4_11zbMath1482.05156OpenAlexW2532447606MaRDI QIDQ2819498

Marie-France Sagot, Blerina Sinaimeri, Mattia Gastaldello, Arnaud Mary, 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

exact exponential algorithmsenumeration algorithmschain subgraph cover problem

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)

Related Items (1)

Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes

Cites Work

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

This page was built for publication: On Maximal Chain Subgraphs and Covers of Bipartite Graphs