Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/138053
14 Visitors
17 Hits
0 Downloads
- Title
- Parameterized graph editing with chosen vertex degrees
- Related
- International Conference on Combinatorial Optimization and Applications (2rd : 2008) (21 - 24 August 2008 : St. John's, N.L.)
- Related
- Yang, Boting; Du, Ding-Zhu and Wang, Cao An. Combinatorial Optimization and Applications : second international conference, Cocoa 2008, St. John's, Canada, August 21-24, 2008 : proceedings, p.13-22
- DOI
- 10.1007/978-3-540-85097-7_2
- Related
- Lecture notes in computer science 5165
- Publisher
- Berlin : New York : Springer-Verlag
- Date
- 2008
- Author/Creator
- Mathieson, Luke
- Author/Creator
- Szeider, Stefan
- Description
- We study the parameterized complexity of the following problem: is it possible to make a given graph r-regular by applying at most k elementary editing operations; the operations are vertex deletion, edge deletion, and edge addition. We also consider more general annotated variants of this problem, where vertices and edges are assigned an integer cost and each vertex v has assigned its own desired degree δ(v)∈ ∈{0,...,r}. We show that both problems are fixed-parameter tractable when parameterized by (k,r), but W[1]-hard when parameterized by k alone. These results extend our earlier results on problems that are defined similarly but where edge addition is not available. We also show that if edge addition and/or deletion are the only available operations, then the problems are solvable in polynomial time. This completes the classification for all combinations of the three considered editing operations.
- Description
- 10 page(s)
- Resource Type
- conference paper
- Organisation
- Macquarie University. Dept. of Computing
- Identifier
- http://hdl.handle.net/1959.14/138053
- Identifier
- ISBN:9783540850960
- Identifier
- ISSN:0302-9743
- Identifier
- mq_res-ext-2-s2.0-51849112313
- Language
- eng
- Reviewed
