Standard

A new view on rural postman based on Eulerian extension and matching. / Sorge, Manuel; Van Bevern, René; Niedermeier, Rolf et al.

Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers. 2011. p. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7056 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Sorge, M, Van Bevern, R, Niedermeier, R & Weller, M 2011, A new view on rural postman based on Eulerian extension and matching. in Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7056 LNCS, pp. 310-323, 22nd International Workshop on Combinatorial Algorithms, IWOCA 2011, Vancouver, BC, Canada, 20.07.2011. https://doi.org/10.1007/978-3-642-25011-8_25

APA

Sorge, M., Van Bevern, R., Niedermeier, R., & Weller, M. (2011). A new view on rural postman based on Eulerian extension and matching. In Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers (pp. 310-323). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7056 LNCS). https://doi.org/10.1007/978-3-642-25011-8_25

Vancouver

Sorge M, Van Bevern R, Niedermeier R, Weller M. A new view on rural postman based on Eulerian extension and matching. In Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers. 2011. p. 310-323. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25011-8_25

Author

Sorge, Manuel ; Van Bevern, René ; Niedermeier, Rolf et al. / A new view on rural postman based on Eulerian extension and matching. Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers. 2011. pp. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{39e44f981dbc4171b993963a6890bdc2,
title = "A new view on rural postman based on Eulerian extension and matching",
abstract = "We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use it to make some partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the number of weakly connected components in the graph induced by the required arcs. This is a more than thirty years open and long-time neglected question with significant practical relevance.",
author = "Manuel Sorge and {Van Bevern}, Ren{\'e} and Rolf Niedermeier and Mathias Weller",
year = "2011",
month = nov,
day = "28",
doi = "10.1007/978-3-642-25011-8_25",
language = "English",
isbn = "9783642250101",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "310--323",
booktitle = "Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers",
note = "22nd International Workshop on Combinatorial Algorithms, IWOCA 2011 ; Conference date: 20-07-2011 Through 22-07-2011",

}

RIS

TY - GEN

T1 - A new view on rural postman based on Eulerian extension and matching

AU - Sorge, Manuel

AU - Van Bevern, René

AU - Niedermeier, Rolf

AU - Weller, Mathias

PY - 2011/11/28

Y1 - 2011/11/28

N2 - We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use it to make some partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the number of weakly connected components in the graph induced by the required arcs. This is a more than thirty years open and long-time neglected question with significant practical relevance.

AB - We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use it to make some partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the number of weakly connected components in the graph induced by the required arcs. This is a more than thirty years open and long-time neglected question with significant practical relevance.

UR - http://www.scopus.com/inward/record.url?scp=81855225396&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25011-8_25

DO - 10.1007/978-3-642-25011-8_25

M3 - Conference contribution

AN - SCOPUS:81855225396

SN - 9783642250101

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 310

EP - 323

BT - Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers

T2 - 22nd International Workshop on Combinatorial Algorithms, IWOCA 2011

Y2 - 20 July 2011 through 22 July 2011

ER -

ID: 22342036