Path-Based Supports for Hypergraphs - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

Path-Based Supports for Hypergraphs

Abstract

A path-based support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a Hamiltonian subgraph. While it is NP-complete to compute a path-based support with the minimum number of edges or to decide whether there is a planar path-based support, we show that a path-based tree support can be computed in polynomial time if it exists.
Fichier principal
Vignette du fichier
brandesIWOCA10b.pdf (251.37 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00538984 , version 1 (02-12-2010)

Identifiers

  • HAL Id : hal-00538984 , version 1

Cite

Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud Sallaberry. Path-Based Supports for Hypergraphs. 21st International Workshop on Combinatorial Algorithms (IWOCA 2010), Jul 2010, United Kingdom. pp.20-33. ⟨hal-00538984⟩

Collections

CNRS INRIA INRIA2
133 View
201 Download

Share

Gmail Facebook X LinkedIn More