Path-Based Supports for Hypergraphs | Zendy

Ulrik Brandes | Zendy; Sabine Cornelsen | Zendy; Barbara Pampel | Zendy; Arnaud Sallaberry | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Path-Based Supports for Hypergraphs

Author(s) -

Ulrik Brandes,

Sabine Cornelsen,

Barbara Pampel,

Arnaud Sallaberry

Publication year - 2011

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/978-3-642-19222-7_3

Subject(s) - hypergraph , path (computing) , hamiltonian path , vertex (graph theory) , induced path , combinatorics , computer science , graph , longest path problem , discrete mathematics , mathematics , shortest path problem , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research