Show simple item record

Author
dc.contributor.author
Király, Tamás 
Author
dc.contributor.author
LC, Lau 
Editor
dc.contributor.editor
&, 
Availability Date
dc.date.accessioned
2015-01-09T11:14:24Z
Availability Date
dc.date.available
2015-01-09T11:14:24Z
Release
dc.date.issued
2006
ISBN
dc.identifier.isbn
0-7695-2720-5
uri
dc.identifier.uri
http://hdl.handle.net/10831/10662
Abstract
dc.description.abstract
Given an undirected hypergraph and a subset of vertices S ⊆ V with a specified root vertex r ∈ S, the STEINER ROOTED-ORIENTATION problem is to find an orientation of all the hyperedges so that in the resulting directed hypergraph the "connectivity" from the root r to the vertices in S is maximized. This is motivated by a multicasting problem in undirected networks as well as a generalization of some classical problems in graph theory. The main results of this paper are the following approximate min-max relations: • Given an undirected hypergraph H, if S is 2k-hyperedge-connected in H, then H has a Steiner rooted k-hyperarc-connected orientation. • Given an undirected graph G, if S is 2k-element-connected in G, then G has a Steiner rooted k-element-connected orientation. Both results are tight in terms of the connectivity bounds. These also give polynomial time constant factor approximation algorithms for both problems. The proofs are based on submodular techniques, and a graph decomposition technique used in the STEINER TREE PACKING problem. Some complementary hardness results are presented at the end. © 2006 IEEE.
Language
dc.language
Angol
Rent
dc.publisher
IEEE Computer Society
Contact information
dc.relation.ispartof
urn:isbn:0-7695-2720-5
Title
dc.title
Approximate min-max theorems of Steiner rooted-orientations of hypergraphs
Type
dc.type
könyvfejezet
Date Change
dc.date.updated
2014-12-16T13:16:14Z
Language
dc.language.rfc3066
eng
Note
dc.description.note
FELTÖLTŐ: Király Tamás - tkiraly@cs.elte.hu FELTÖLTÉSI MEGJEGYZÉS: Technical Report változat
Scope
dc.format.page
283-292
Address Book
dc.identifier.booktitle
47th Annual IEEE Symposium on Foundations of Computer Science
Doi ID
dc.identifier.doi
10.1109/FOCS.2006.12
Wos ID
dc.identifier.wos
000242526200027
ID Scopus
dc.identifier.scopus
38749095220
MTMT ID
dc.identifier.mtmt
2202326
abbreviated journal
dc.identifier.jabbrev
ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE
Release Date
dc.description.issuedate
2006
Author institution
dc.contributor.department
ELTE/ELTE TTK/ELTE TTK MI/MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport


Files in this item


Approximate min-max theorems of Steiner rooted-orientations of hypergraphs
 

This item appears in the following Collection(s)

Show simple item record