On the complexity of minimum maximal acyclic matchings. (English) Zbl 07929164
MSC:
90Cxx
Found 104 Documents (Results 1–100)
Cutting Barnette graphs perfectly is hard. (English) Zbl 07898962
MSC:
68Qxx
A bisection approach to subcubic maximum induced matching. (English) Zbl 07883874
Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 18th international conference and workshops on algorithms and computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024. Proceedings. Singapore: Springer. Lect. Notes Comput. Sci. 14549, 257-272 (2024).
MSC:
68Wxx
\( \mathcal{P} \)-matchings parameterized by treewidth. (English) Zbl 07842214
Paulusma, Daniël (ed.) et al., Graph-theoretic concepts in computer science. 49th international workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 14093, 217-231 (2023).
MSC:
68R10
Parameterized results on acyclic matchings with implications for related problems. (English) Zbl 07842213
Paulusma, Daniël (ed.) et al., Graph-theoretic concepts in computer science. 49th international workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 14093, 201-216 (2023).
MSC:
68R10
Cutting Barnette graphs perfectly is hard. (English) Zbl 07842207
Paulusma, Daniël (ed.) et al., Graph-theoretic concepts in computer science. 49th international workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 14093, 116-129 (2023).
MSC:
68R10
Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model. (English) Zbl 1512.68218
A characterization of well-indumatchable graphs having girth greater than seven. (English) Zbl 1497.05216
Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs. (English) Zbl 1535.68213
Vertex cover at distance on \(H\)-free graphs. (English) Zbl 07495026
Flocchini, Paola (ed.) et al., Combinatorial algorithms. 32nd international workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12757, 237-251 (2021).
Efficient algorithms for maximum induced matching problem in permutation and trapezoid graphs. (English) Zbl 1522.68416
Maximum weight induced matching in some subclasses of bipartite graphs. (English) Zbl 1466.90091
MSC:
90C27
Approximating maximum acyclic matchings by greedy and local search strategies. (English) Zbl 07336133
Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 542-553 (2020).
MSC:
68Rxx
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more. (English) Zbl 1452.68083
On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs. (English) Zbl 1442.05175
MSC:
05C70
Multi-channel assignment and link scheduling for prioritized latency-sensitive applications. (English) Zbl 1543.90065
Dressler, Falko (ed.) et al., Algorithms for sensor systems. 15th international symposium on algorithms and experiments for wireless sensor networks, ALGOSENSORS 2019, Munich, Germany, September 12–13, 2019. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11931, 137-157 (2019).
On the computational complexity of the Helly number in the \(P_3\) and related convexities. (English) Zbl 07515188
Coutinho, Gabriel (ed.) et al., Proceedings of LAGOS 2019, the tenth Latin and American algorithms, graphs and optimization symposium, Belo Horizonte, Brazil, June 2–7 2019. Amsterdam: Elsevier. Electron. Notes Theor. Comput. Sci. 346, 285-297 (2019).
On some hard and some tractable cases of the maximum acyclic matching problem. (English) Zbl 1431.05121
On the hardness of deciding the equality of the induced and the uniquely restricted matching number. (English) Zbl 1473.05291
Integer programming formulations and Benders decomposition for the maximum induced matching problem. (English) Zbl 1528.90153
Improved kernels for several problems on planar graphs. (English) Zbl 1446.68075
Chen, Jianer (ed.) et al., Frontiers in algorithmics. 12th international workshop, FAW 2018, Guangzhou, China, May 8–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10823, 169-180 (2018).
Complexity of generation. (English) Zbl 1484.68069
Fomin, Fedor V. (ed.) et al., Computer science – theory and applications. 13th international computer science symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10846, 1-14 (2018).
On perfect linegraph squares. (English) Zbl 1519.05088
Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 44th international workshop, WG 2018, Cottbus, Germany, June 27–29, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11159, 252-265 (2018).
Efficient domination and efficient edge domination: a brief survey. (English) Zbl 1400.05170
Panda, B. S. (ed.) et al., Algorithms and discrete applied mathematics. 4th international conference, CALDAM 2018, Guwahati, India, February 15–17, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-74179-6/pbk; 978-3-319-74180-2/ebook). Lecture Notes in Computer Science 10743, 1-14 (2018).
Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time. (English) Zbl 1377.05185
Maximum induced matching algorithms via vertex ordering characterizations. (English) Zbl 1457.68217
Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 43, 12 p. (2017).
Parameterized algorithms and kernels for rainbow matching. (English) Zbl 1435.68237
Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 71, 13 p. (2017).
Induced matching in some subclasses of bipartite graphs. (English) Zbl 1485.68196
Gaur, Daya (ed.) et al., Algorithms and discrete applied mathematics. Third international conference, CALDAM 2017, Sancoale, Goa, India, February 16–18, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10156, 308-319 (2017).
On minimum maximal distance-\(k\) matchings. (English) Zbl 1355.68123
Korpelainen, Nicholas (ed.), TCDM 2016. Proceedings of the 1st IMA conference on theoretical and computational discrete mathematics, University of Derby, Derby, UK, March 22–23, 2016. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 56, 71-76 (2016).
Almost induced matching: linear kernels and parameterized algorithms. (English) Zbl 1417.05170
Heggernes, Pinar (ed.), Graph-theoretic concepts in computer science. 42nd international workshop, WG 2016, Istanbul, Turkey, June 22–24, 2016. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 9941, 220-232 (2016).
Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks. (Russian. English summary) Zbl 1506.05175
Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth. (Russian. English summary) Zbl 1432.05081
On graphs with induced matching number almost equal to matching number. (English) Zbl 1347.05155
Campêlo, Manoel (ed.) et al., LAGOS ’15. Selected papers of the 8th Latin-American algorithms, graphs, and optimization symposium, Praia das Fontes, Beberibe, Brazil, May 11–15, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 50, 9-14, electronic only (2015).
Moderately exponential time algorithms for the maximum induced matching problem. (English) Zbl 1327.90350
On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs. (English) Zbl 1320.05125
Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph. (Russian. English summary) Zbl 1462.05301
Maximum induced matchings in grids. (English) Zbl 1375.05219
Migdalas, Athanasios (ed.) et al., Optimization theory, decision making, and operations research applications. Proceedings of the 1st international symposium and 10th Balkan conference on operational research, Thessaloniki, Greece, September 22–25, 2011. New York, NY: Springer (ISBN 978-1-4614-5133-4/hbk; 978-1-4614-5134-1/ebook). Springer Proceedings in Mathematics & Statistics 31, 177-187 (2013).
MSC:
05C70
A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem. (English) Zbl 1348.90592
On distance-3 matchings and induced matchings. (English) Zbl 1210.05105
MSC:
05C70
Improved induced matchings in sparse graphs. (English) Zbl 1273.68165
Chen, Jianer (ed.) et al., Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-11268-3/pbk). Lecture Notes in Computer Science 5917, 134-148 (2009).
On distance-3 matchings and induced matchings. (English) Zbl 1194.05122
Lipshteyn, Marina (ed.) et al., Graph theory, computational intelligence and thought. Essays dedicated to Martin Charles Golumbic on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-02028-5/pbk). Lecture Notes in Computer Science 5420, 116-126 (2009).
Efficient edge domination in regular graphs. (English) Zbl 1210.05094
MSC:
05C69
Approximability results for the maximum and minimum maximal induced matching problems. (English) Zbl 1140.90479
A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree. (Russian. English summary) Zbl 1497.05249
Squares of intersection graphs and induced matchings. (English) Zbl 1202.05112
Meszka, Mariusz (ed.), Fifth Cracow conference on graph theory, USTRON ’06, Ustroń, Poland, September 11–15, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 24, 223-230 (2006).
Independent packings in structured graphs. (English) Zbl 1078.05067
MSC:
05C70
The graphs with maximum induced matching and maximum matching the same size. (English) Zbl 1073.05054
A polynomial time algorithm for strong edge coloring of partial \(k\)-trees. (English) Zbl 1062.68091
An inequality for polymatroid functions and its applications. (English) Zbl 1033.05023
Reviewer: James F. Lawrence (Fairfax)
Finding a maximum induced matching in weakly chordal graphs. (English) Zbl 1022.05064
Reviewer: Bal Kishan Dass (Delhi)
Maximum induced matchings of random cubic graphs. (English) Zbl 1001.05093
Reviewer: Ralph J.Faudree (Memphis)
The efficiency of AC graphs. (English) Zbl 0788.68106
Reviewer: S.V.Duzhin (Pereslavl’-Zalesskij)
Filter Results by …
Document Type
- Journal Articles (82)
- Collection Articles (22)
all
top 5
Author
- Rautenbach, Dieter (12)
- Brandstädt, Andreas (5)
- Cameron, Kathie (5)
- Fürst, Maximilian (5)
- Joos, Felix Claudius (5)
- Zehavi, Meirav (5)
- Baste, Julien (4)
- Chaudhary, Juhi (4)
- Orlovich, Yuriĭ Leonidovich (4)
- Duckworth, William (3)
- Gupta, Sushmita (3)
- Mosca, Raffaele (3)
- Panda, Bhawani Sankar (3)
- Roy, Sanjukta (3)
- Saurabh, Saket (3)
- Xiao, Mingyu (3)
- Zito, Michele (3)
- Bonnet, Edouard (2)
- Cardoso, Domingos Moreira (2)
- Chakraborty, Dibyayan (2)
- Dane, Piyush (2)
- Draque Penso, Lucia (2)
- Duarte, Marcio Antônio (2)
- Duron, Julien (2)
- Ekim, Tınaz (2)
- Erman, Rok (2)
- Feng, Qilong (2)
- Finke, Gerd (2)
- Gordon, Valery S. (2)
- Gurvich, Vladimir A. (2)
- Habib, Michel (2)
- Huang, Neng (2)
- Kashyap, Manav (2)
- Kou, Shaowei (2)
- Kowalik, Łukasz (2)
- Krnc, Matjaž (2)
- Mouatadid, Lalla (2)
- Pandey, Arti (2)
- Sritharan, R. (2)
- Tan, Guanlan (2)
- Waleń, Tomasz (2)
- Wang, Jianxin (2)
- Werner, Frank (2)
- Wormald, Nicholas Charles (2)
- Zhuo, Beilin (2)
- Zverovich, Igor’ Èdmundovich (2)
- Adefokun, Tayo Charles (1)
- Agrawal, Akanksha (1)
- Ahat, Betül (1)
- Ajayi, Deborah Olayide A. (1)
- Aravind, N. R. (1)
- Avis, David M. (1)
- Baptiste, Philippe (1)
- Bermond, Jean-Claude (1)
- Bhattacharjee, Sutanay (1)
- Blair, Jean R. S. (1)
- Boros, Endre (1)
- Bujtás, Csilla (1)
- Carvalho, Moisés Teles jun. (1)
- Cerdeira, Jorge Orestes (1)
- Chalermsook, Parinya (1)
- Chang, Jou-Ming (1)
- Chang, Maw-Shang (1)
- Chen, Li-Hsuan (1)
- Chen, Yan (1)
- Chowdhury, Rezaul Alam (1)
- Christou, Ioannis T. (1)
- Cygan, Marek (1)
- Dallard, Clément (1)
- Dantas, Simone (1)
- Delorme, Charles (1)
- Deng, Kecai (1)
- Díaz, Josep (1)
- Do, Phan-Thuan (1)
- Dolgui, Alexandre B. (1)
- dos Santos Souza, Uéverton (1)
- Dourado, Mitre Costa (1)
- Elbassioni, Khaled M. (1)
- Erveš, Rija (1)
- Finbow, Arthur S. (1)
- Fukunaga, Takuro (1)
- Ganesan, Ashwin (1)
- Gao, Jie (1)
- Ghafoor, Arif (1)
- Ghanbari, Nima (1)
- Ghodrati, Amir Hossein (1)
- Goddard, Wayne Dean (1)
- Hajebi, Sahab (1)
- Hartnell, Bert L. (1)
- Hatzel, Meike (1)
- Hedetniemi, Sandra Lee Mitchell (1)
- Hedetniemi, Stephen Travis (1)
- Hell, Pavol (1)
- Henning, Michael Anthony (1)
- Hoàng, Chính T. (1)
- Hoi, Gordon (1)
- Huang, Chien-Chung (1)
- Huang, Sumin (1)
- Hung, Ling-Ju (1)
- Jain, Sanjay (1)
- and 82 more Authors
all
top 5
Serial
- Discrete Appl. Math. (20)
- Theor. Comput. Sci. (13)
- Discrete Math. (8)
- Algorithmica (6)
- Tr. Inst. Mat., Minsk (4)
- J. Comb. Optim. (3)
- J. Discrete Algorithms (3)
- Inf. Process. Lett. (2)
- SIAM J. Discrete Math. (2)
- Discrete Optim. (2)
- Discrete Math. Algorithms Appl. (2)
- Inf. Sci. (1)
- J. Comput. Appl. Math. (1)
- J. Comput. Syst. Sci. (1)
- J. Sov. Math. (1)
- SIAM J. Comput. (1)
- Acta Math. Appl. Sin., Engl. Ser. (1)
- Inf. Comput. (1)
- Comput. Oper. Res. (1)
- Ann. Oper. Res. (1)
- Math. Program. (1)
- Australas. J. Comb. (1)
- Acta Univ. M. Belii, Ser. Math. (1)
- INFORMS J. Comput. (1)
- Fundam. Inform. (1)
- Bull. Malays. Math. Sci. Soc. (2) (1)
- Optim. Lett. (1)
- Comput. Sci. Rev. (1)
