Zobrazeno 1 - 10
of 201
pro vyhledávání: '"Maximilian Fürst"'
(1772 - 1816), Generalmajor und Mäzen
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______386::2da51a12fde0bea5d3dc65eaadda9835
http://epub.oeaw.ac.at/oebl/oebl_L/Lobkowitz_Josef-Franz-Maximilian_1772_1816.xml
http://epub.oeaw.ac.at/oebl/oebl_L/Lobkowitz_Josef-Franz-Maximilian_1772_1816.xml
Autor:
Dieter Rautenbach, Maximilian Fürst
Publikováno v:
Theoretical Computer Science. 804:126-138
For a matching M in a graph G, let G ( M ) be the subgraph of G induced by the vertices of G that are incident with an edge in M. The matching M is induced, if G ( M ) is 1-regular, and M is uniquely restricted, if M is the unique perfect matching of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::77f4b30c9e7a1f468f3a4464b1e4977e
https://doi.org/10.1016/j.tcs.2019.11.020
https://doi.org/10.1016/j.tcs.2019.11.020
Autor:
Maximilian Fürst
Publikováno v:
Information Processing Letters. 147:77-81
If G ( M ) denotes the subgraph of a graph G induced by the set of vertices that are covered by some matching M in G, then M is an induced or a uniquely restricted matching if G ( M ) is 1-regular or if M is the unique perfect matching of G ( M ) , r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8fdfc40a17d4c44a226cef213310014f
https://doi.org/10.1016/j.ipl.2019.03.011
https://doi.org/10.1016/j.ipl.2019.03.011
Publikováno v:
Discrete Applied Mathematics. 262:189-194
A matching M in a graph G is uniquely restricted if no other matching in G covers the same set of vertices. We conjecture that every connected subcubic graph with m edges and b bridges that is distinct from K 3 , 3 has a uniquely restricted matching
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0e6303979aa6d9b1df9c7fa9e1ec7827
https://doi.org/10.1016/j.dam.2019.02.013
https://doi.org/10.1016/j.dam.2019.02.013
Autor:
Maximilian Fürst, Dieter Rautenbach
Publikováno v:
Graphs and Combinatorics. 35:353-361
A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. We establish tight lower bounds on the maximum size of a uniquely restricted matching in terms of order, size, and maximum degree.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::af3b6384c4c9021ebe3611aa2eacb88c
https://doi.org/10.1007/s00373-018-1991-8
https://doi.org/10.1007/s00373-018-1991-8
Publikováno v:
Discrete Optimization
Discrete Optimization, Elsevier, 2020, 38, pp.100593. ⟨10.1016/j.disopt.2020.100593⟩
Discrete Optimization, Elsevier, 2020, 38, pp.100593. ⟨10.1016/j.disopt.2020.100593⟩
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (2018) provide an approximation algorithm with ratio Δ for the weighted version of the induced mat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5953670993f2b08a1ba6f85c1886f41c
https://hal.archives-ouvertes.fr/hal-03470079
https://hal.archives-ouvertes.fr/hal-03470079
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2020, 285, pp.343-349. ⟨10.1016/j.dam.2020.05.030⟩
Discrete Applied Mathematics, Elsevier, 2020, 285, pp.343-349. ⟨10.1016/j.dam.2020.05.030⟩
We propose the conjecture that the domination number γ ( G ) of a Δ -regular graph G with Δ ≥ 1 is always at most its edge domination number γ e ( G ) , which coincides with the domination number of its line graph. We prove that γ ( G ) ≤ 1
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9cc741948a5acaafa135aab5fb3c7102
https://hal.archives-ouvertes.fr/hal-03470076
https://hal.archives-ouvertes.fr/hal-03470076
Publikováno v:
Computing and Combinatorics
Computing and Combinatorics, 12273 (3), Springer International Publishing; Springer International Publishing, pp.542-553, 2020, Lecture Notes in Computer Science, ⟨10.1007/978-3-030-58150-3_44⟩
Lecture Notes in Computer Science ISBN: 9783030581497
COCOON
Computing and Combinatorics, 12273 (3), Springer International Publishing; Springer International Publishing, pp.542-553, 2020, Lecture Notes in Computer Science, ⟨10.1007/978-3-030-58150-3_44⟩
Lecture Notes in Computer Science ISBN: 9783030581497
COCOON
A matching M in a graph G is acyclic if the subgraph of G induced by the vertices that are incident to an edge in M is a forest. Even restricted to graphs of bounded maximum degree, the maximum acyclic matching problem is hard. We contribute efficien
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b891788b5896ac121daf0ad788bd302c
https://hal.archives-ouvertes.fr/hal-03470113
https://hal.archives-ouvertes.fr/hal-03470113
Publikováno v:
Information Processing Letters, 139, 60-63. Elsevier Science
Maastricht University
Maastricht University
Combining known results it follows that deciding whether a given graph G of size m has a unique perfect matching as well as finding that matching if it exists, can be done in time O(m) if G is either a cograph, or a split graph, or a claw-free graph.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::27371ddf327aba174cacaf7710a78192
https://doi.org/10.1016/j.ipl.2018.07.008
https://doi.org/10.1016/j.ipl.2018.07.008