Induced matchings in subcubic planar graphs
| Autor: | Kang, R.J., Mnich, M., Müller, T., Berg, de, M., Meyer, U. |
|---|---|
| Přispěvatelé: | Combinatorial Optimization 1, Networks and Optimization, Stochastic Operations Research |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Matching (graph theory) General Mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences subcubic planar graphs Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols induced matchings strong chromatic index Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Algorithms – ESA 2010 ISBN: 9783642157806 ESA (2) Algorithms-ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II, 112-122 STARTPAGE=112;ENDPAGE=122;TITLE=Algorithms-ESA 2010 SIAM Journal on Discrete Mathematics, 26(3), 1383-1411. Society for Industrial and Applied Mathematics (SIAM) Siam Journal on Discrete Mathematics, 26(3), 1383-1411. SIAM Publications SIAM Journal on Discrete Mathematics, 26(3), 1383-1411 Algorithms-ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II), 112-122 STARTPAGE=112;ENDPAGE=122;TITLE=Algorithms-ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II) |
| ISSN: | 0302-9743 0895-4801 |
| DOI: | 10.1007/978-3-642-15781-3_10 |
| Popis: | We present a linear-time algorithm that, given a planar graph with m edges and maximum degree 3, finds an induced matching of size at least m/9. This is best possible. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|