Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs

DOI10.1016/j.tcs.2012.09.010zbMath1253.05090OpenAlexW1985640436MaRDI QIDQ1929213

Mohammad Ali Safari

Publication date: 7 January 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.09.010

zbMATH Keywords

connectivityhypergraphsmulticutminimum vertex coverminimum dominating sethyper-D-widthhyper-T-decompositionshyper-T-width

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

Cites Work

• Unnamed Item
• Hypertree decompositions and tractable queries
• On complexity of single-minded auction
• Directed tree-width
• Fixed-parameter approximation: conceptual framework and approximability results
• Easy problems for tree-decomposable graphs
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs