Search results for "subcubic"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
97	Harold N. Gabow, San Skulrattanakulchai	Coloring Algorithms on Subcubic Graphs.	COCOON	2002	DBLP DOI BibTeX RDF
58	Erich L. Kaltofen	An output-sensitive variant of the baby steps/giant steps determinant algorithm.	ISSAC	2002	DBLP DOI BibTeX RDF
41	Elham Aboomahigir, Milad Ahanjideh, Saieed Akbari	Decomposing claw-free subcubic graphs and 4-chordal subcubic graphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
39	Swarat Chaudhuri	Subcubic algorithms for recursive state machines.	POPL	2008	DBLP DOI BibTeX RDF	CFL-reachability, cubic bottleneck, recursive state machines, transitive closure, interprocedural analysis, context-free languages, pushdown systems
38	Timothy M. Chan	More algorithms for all-pairs shortest paths in weighted graphs.	STOC	2007	DBLP DOI BibTeX RDF	computational geometry, shortest paths, graph algorithms, matrix multiplication
38	Lillian Lee	Fast context-free grammar parsing requires fast boolean matrix multiplication.	J. ACM	2002	DBLP DOI BibTeX RDF	context-free grammar parsing, Boolean matrix multiplication
33	Virginia Vassilevska, Ryan Williams 0001, Raphael Yuster	All-pairs bottleneck paths for general graphs in truly sub-cubic time.	STOC	2007	DBLP DOI BibTeX RDF	bottleneck path, maximum capacity path, matrix multiplication, subcubic
33	Noga Alon, Zvi Galil, Oded Margalit, Moni Naor	Witnesses for Boolean Matrix Multiplication and for Shortest Paths	FOCS	1992	DBLP DOI BibTeX RDF	subcubic methods, shortest paths, deterministic algorithm, transitive closure, witnesses, Boolean matrix multiplication
20	Carl Feghali, Robert Sámal	Decomposing a triangle-free planar graph into a forest and a subcubic forest.	Eur. J. Comb.	2024	DBLP DOI BibTeX RDF
20		A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications.	CoRR	2024	DBLP DOI BibTeX RDF
20	Yuzhenni Wang, Xiao-Dong Zhang 0001	A note on median eigenvalues of subcubic graphs.	Discret. Appl. Math.	2024	DBLP DOI BibTeX RDF
20	Gordon Hoi, Sanjay Jain 0001, Ammar Fathin Sabili, Frank Stephan 0001	A Bisection Approach to Subcubic Maximum Induced Matching.	WALCOM	2024	DBLP DOI BibTeX RDF
20	Michael C. Wigal, Youngho Yoo, Xingxing Yu	Approximating TSP walks in subcubic graphs.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
20	Amir Abboud, Fabrizio Grandoni 0001, Virginia Vassilevska Williams	Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
20	Nicolas Gast, Bruno Gaujal, Kimang Khun	Testing indexability and computing Whittle and Gittins index in subcubic time.	Math. Methods Oper. Res.	2023	DBLP DOI BibTeX RDF
20	Yuquan Lin, Wensong Lin	The Tight Bound for the Strong Chromatic Indices of Claw-Free Subcubic Graphs.	Graphs Comb.	2023	DBLP DOI BibTeX RDF
20	Matthew Johnson 0002, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
20	Krzysztof Pióro	Subcubic algorithm for (Unweighted) Unrooted Tree Edit Distance.	CoRR	2023	DBLP DOI BibTeX RDF
20	Borut Luzar, Mária Maceková, Simona Rindosová, Roman Soták, Katarína Sroková, Kenny Storgel	Locally irregular edge-coloring of subcubic graphs.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
20	Wei Yang, Baoyindureng Wu	On packing S-colorings of subcubic graphs.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
20	János Barát, Zoltán L. Blázsik, Gábor Damásdi	Crumby colorings - Red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen.	Discret. Math.	2023	DBLP DOI BibTeX RDF
20	Lei Zhang, Jianhua Tu, Chunlin Xin	Maximum dissociation sets in subcubic trees.	J. Comb. Optim.	2023	DBLP DOI BibTeX RDF
20	Xujun Liu, Michael Santana, Taylor Short	Every subcubic multigraph is (1,27) $(1,{2}^{7})$-packing edge-colorable.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
20	Krzysztof Pióro	Subcubic Algorithm for (Unweighted) Unrooted Tree Edit Distance.	ESA	2023	DBLP DOI BibTeX RDF
20	Matthew Johnson 0002, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen	Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs.	MFCS	2023	DBLP DOI BibTeX RDF
20	Dmitry Chistikov 0001, Rupak Majumdar, Philipp Schepper	Subcubic certificates for CFL reachability.	Proc. ACM Program. Lang.	2022	DBLP DOI BibTeX RDF
20	Lily Chen, Yanyi Li	A New Proof for a Result on the Inclusion Chromatic Index of Subcubic Graphs.	Axioms	2022	DBLP DOI BibTeX RDF
20	Hanlin Ren	Improved distance sensitivity oracles with subcubic preprocessing time.	J. Comput. Syst. Sci.	2022	DBLP DOI BibTeX RDF
20	Jian-Bo Lv, Jianxi Li, Xiaoxia Zhang	On Strong Edge-Coloring of Claw-Free Subcubic Graphs.	Graphs Comb.	2022	DBLP DOI BibTeX RDF
20	Ammar Babikir, Michael A. Henning	Triangles and (Total) Domination in Subcubic Graphs.	Graphs Comb.	2022	DBLP DOI BibTeX RDF
20	Wei Yang, Baoyindureng Wu	Broadcast Domination in Subcubic Graphs.	Graphs Comb.	2022	DBLP DOI BibTeX RDF
20	Gordon Hoi, Ammar Fathin Sabili, Frank Stephan 0001	An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs.	CoRR	2022	DBLP BibTeX RDF
20	Borut Luzar, Mária Maceková, Simona Rindosová, Roman Soták, Katarína Sroková, Kenny Storgel	Locally irregular edge-coloring of subcubic graphs.	CoRR	2022	DBLP DOI BibTeX RDF
20	Sabine Storandt, Johannes Zink 0001	Polyline Simplification under the Local Fréchet Distance has Subcubic Complexity in 2D.	CoRR	2022	DBLP BibTeX RDF
20	Matthew Johnson 0002, Barnaby Martin, Siani Smith, Sukanya Pandey, Daniël Paulusma, Erik Jan van Leeuwen	Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs.	CoRR	2022	DBLP DOI BibTeX RDF
20	Nicolas Gast, Bruno Gaujal, Kimang Khun	Computing Whittle (and Gittins) Index in Subcubic Time.	CoRR	2022	DBLP DOI BibTeX RDF
20	Qing Cui, Zhenmeng Han	List star edge-coloring of claw-free subcubic multigraphs.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
20	Baya Ferdjallah, Samia Kerdjoudj, André Raspaud	Injective edge-coloring of subcubic graphs.	Discret. Math. Algorithms Appl.	2022	DBLP DOI BibTeX RDF
20	Sebastien Bonduelle, Frantisek Kardos	Subcubic planar graphs of girth 7 are class I.	Discret. Math.	2022	DBLP DOI BibTeX RDF
20	Amirreza Akbari, Saieed Akbari, Ali Doosthosseini, Z. Hadizadeh, Michael A. Henning, A. Naraghi	Independent domination in subcubic graphs.	J. Comb. Optim.	2022	DBLP DOI BibTeX RDF
20	Hervé Hocquard, Dimitri Lajou, Borut Luzar	Between proper and strong edge-colorings of subcubic graphs.	J. Graph Theory	2022	DBLP DOI BibTeX RDF
20	Renzo Gómez, Flávio Keidi Miyazawa, Yoshiko Wakabayashi	Minimum t-Spanners on Subcubic Graphs.	WALCOM	2022	DBLP DOI BibTeX RDF
20	Marthe Bonamy, François Dross, Tomás Masarík, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk	Jones' Conjecture in Subcubic Graphs.	Electron. J. Comb.	2021	DBLP DOI BibTeX RDF
20	Katarzyna Paluch 0001, Mateusz Wasylkiewicz	A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges.	Inf. Process. Lett.	2021	DBLP DOI BibTeX RDF
20	Xue-Gang Chen, Yu-Feng Wang, Xiao-Fei Wu	Hereditary equality of domination and exponential domination in subcubic graphs.	Discuss. Math. Graph Theory	2021	DBLP DOI BibTeX RDF
20	Philipp Kindermann, Fabrizio Montecchiani, Lena Schlipf, André Schulz 0001	Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles.	J. Graph Algorithms Appl.	2021	DBLP DOI BibTeX RDF
20	Jing Gu, Weifan Wang 0001, Yiqiao Wang 0002, Ying Wang	Strict Neighbor-Distinguishing Index of Subcubic Graphs.	Graphs Comb.	2021	DBLP DOI BibTeX RDF
20	Davide Mattiolo, Giuseppe Mazzuoccolo	On 3-Bisections in Cubic and Subcubic Graphs.	Graphs Comb.	2021	DBLP DOI BibTeX RDF
20	Dmitry Chistikov 0001, Rupak Majumdar, Philipp Schepper	Subcubic Certificates for CFL Reachability.	CoRR	2021	DBLP BibTeX RDF
20	Amir Abboud, Robert Krauthgamer, Jason Li 0006, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi	Gomory-Hu Tree in Subcubic Time.	CoRR	2021	DBLP BibTeX RDF
20	Michael C. Wigal, Youngho Yoo, Xingxing Yu	Approximating TSP walks in subcubic graphs.	CoRR	2021	DBLP BibTeX RDF
20	Sebastien Bonduelle, Frantisek Kardos	Subcubic planar graphs of girth 7 are class I.	CoRR	2021	DBLP BibTeX RDF
20	Hoang La, Mickaël Montassier	2-distance 4-coloring of planar subcubic graphs with girth at least 21.	CoRR	2021	DBLP BibTeX RDF
20	Alexandr V. Kostochka, Xujun Liu	Packing (1, 1, 2, 4)-coloring of subcubic outerplanar graphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
20	Florent Foucaud, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Éric Sopena, Petru Valicov	Exact square coloring of subcubic planar graphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
20	Jian-Bo Lv, Jianxi Li, Nian Hong Zhou	List injective edge-coloring of subcubic graphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
20	Carl Johan Casselgren, Jonas B. Granholm, André Raspaud	On star edge colorings of bipartite and subcubic graphs.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
20	Stéphane Bessy, Johannes Pardey, Dieter Rautenbach	Exponential independence in subcubic graphs.	Discret. Math.	2021	DBLP DOI BibTeX RDF
20	Xinhong Pang, Jingjing Huo, Min Chen 0012, Weifan Wang 0001	A note on strong edge choosability of toroidal subcubic graphs.	Australas. J Comb.	2021	DBLP BibTeX RDF
20	Wenying Xi, Wensong Lin	On maximum P3-packing in claw-free subcubic graphs.	J. Comb. Optim.	2021	DBLP DOI BibTeX RDF
20	Michael A. Henning, Zekhaya B. Shozi	A characterization of the subcubic graphs achieving equality in the Haxell-Scott lower bound for the matching number.	J. Graph Theory	2021	DBLP DOI BibTeX RDF
20	Maximilian Fürst, Dieter Rautenbach	Uniquely restricted matchings in subcubic graphs without short cycles.	J. Graph Theory	2021	DBLP DOI BibTeX RDF
20	Laurent Bulteau, Guillaume Fertin, Anthony Labarre, Romeo Rizzi, Irena Rusu	Decomposing subcubic graphs into claws, paths or triangles.	J. Graph Theory	2021	DBLP DOI BibTeX RDF
20	Amir Abboud, Robert Krauthgamer, Ohad Trabelsi	Subcubic algorithms for Gomory-Hu tree in unweighted graphs.	STOC	2021	DBLP DOI BibTeX RDF
20	Zahed Rahmati, Fatemeh Emami	RAC drawings in subcubic area.	Inf. Process. Lett.	2020	DBLP DOI BibTeX RDF
20	Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann	Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can).	ACM Trans. Algorithms	2020	DBLP DOI BibTeX RDF
20	Maximilian Fürst, Dieter Rautenbach	On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
20	Ararat Harutyunyan, Michael Lampis, Vadim V. Lozin, Jérôme Monnot	Maximum independent sets in subcubic graphs: New results.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
20	Qing Cui	Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets.	Graphs Comb.	2020	DBLP DOI BibTeX RDF
20	Hanlin Ren	Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.	CoRR	2020	DBLP BibTeX RDF
20	Hervé Hocquard, Dimitri Lajou, Borut Luzar	Between proper and strong edge-colorings of subcubic graphs.	CoRR	2020	DBLP BibTeX RDF
20	Florent Foucaud, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Éric Sopena, Petru Valicov	Exact square coloring of subcubic planar graphs.	CoRR	2020	DBLP BibTeX RDF
20	Amirreza Akbari, Saieed Akbari, Ali Doosthosseini, Z. Hadizadeh, Michael A. Henning, A. Naraghi	Independent Domination in Subcubic Graphs.	CoRR	2020	DBLP BibTeX RDF
20	Katarzyna Paluch 0001, Mateusz Wasylkiewicz	A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges.	CoRR	2020	DBLP BibTeX RDF
20	Amir Abboud, Robert Krauthgamer, Ohad Trabelsi	Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs.	CoRR	2020	DBLP BibTeX RDF
20	Zahed Rahmati, Fatemeh Emami	RAC Drawings in Subcubic Area.	CoRR	2020	DBLP BibTeX RDF
20	Ojas Parekh, Cynthia A. Phillips, Conrad D. James, James B. Aimone	Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication.	CoRR	2020	DBLP BibTeX RDF
20	Piotr Krysta, Mathieu Mari, Nan Zhi	Ultimate greedy approximation of independent sets in subcubic graphs.	CoRR	2020	DBLP BibTeX RDF
20	Michael A. Henning, Gary MacGillivray, Frank Yang	2-limited broadcast domination in subcubic graphs.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
20	Runrun Liu, Xujun Liu, Martin Rolek, Gexin Yu	Packing (1, 1, 2, 2)-coloring of some subcubic graphs.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
20	R. Khoeilar, Hossein Karami 0002, Mustapha Chellali, Seyed Mahmoud Sheikholeslami, Lutz Volkmann	A proof of a conjecture on the differential of a subcubic graph.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
20	Qing Cui, Wenzhong Liu	A note on 3-bisections in subcubic graphs.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
20	Giuseppe Lancia, Marcello Dalpasso	Finding the Best 3-OPT Move in Subcubic Time.	Algorithms	2020	DBLP DOI BibTeX RDF
20	Virginia Vassilevska Williams, Yinzhan Xu	Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications.	SODA	2020	DBLP DOI BibTeX RDF
20	Piotr Krysta, Mathieu Mari, Nan Zhi	Ultimate greedy approximation of independent sets in subcubic graphs.	SODA	2020	DBLP DOI BibTeX RDF
20	Hanlin Ren	Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.	ESA	2020	DBLP DOI BibTeX RDF
20	Hervé Hocquard, Dimitri Lajou, Borut Luzar	Between Proper and Strong Edge-Colorings of Subcubic Graphs.	IWOCA	2020	DBLP DOI BibTeX RDF
20	Shiri Chechik, Sarel Cohen	Distance sensitivity oracles with subcubic preprocessing time and fast query time.	STOC	2020	DBLP DOI BibTeX RDF
20	Celso A. Weffort-Santos, C. N. Campos, Rafael C. S. Schouery	On the Complexity of Gap-[2]-vertex-labellings of Subcubic Bipartite Graphs.	LAGOS	2019	DBLP DOI BibTeX RDF
20	Min Chen 0012, André Raspaud	Acyclic improper choosability of subcubic graphs.	Appl. Math. Comput.	2019	DBLP DOI BibTeX RDF
20	Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani, Mohammad Taghi Hajiaghayi, Saeed Seddighin	Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems.	CoRR	2019	DBLP BibTeX RDF
20	Virginia Vassilevska Williams, Yinzhan Xu	Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications.	CoRR	2019	DBLP BibTeX RDF
20	Marthe Bonamy, François Dross, Tomás Masarík, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk	Jones' Conjecture in subcubic graphs.	CoRR	2019	DBLP BibTeX RDF
20	Maximilian Fürst, Michael A. Henning, Dieter Rautenbach	Uniquely restricted matchings in subcubic graphs.	Discret. Appl. Math.	2019	DBLP DOI BibTeX RDF
20	Nicolas Gastineau, Premysl Holub, Olivier Togni	On the packing chromatic number of subcubic outerplanar graphs.	Discret. Appl. Math.	2019	DBLP DOI BibTeX RDF
20	Karl Bringmann, Fabrizio Grandoni 0001, Barna Saha, Virginia Vassilevska Williams	Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.	SIAM J. Comput.	2019	DBLP DOI BibTeX RDF
20	Borut Luzar, Martina Mockovciaková, Roman Soták	Note on list star edge-coloring of subcubic graphs.	J. Graph Theory	2019	DBLP DOI BibTeX RDF
20	Douglas R. Woodall	The average degree of a subcubic edge?chromatic critical graph.	J. Graph Theory	2019	DBLP DOI BibTeX RDF
20	Ararat Harutyunyan, Michael Lampis, Vadim V. Lozin, Jérôme Monnot	Maximum Independent Sets in Subcubic Graphs: New Results.	WG	2019	DBLP DOI BibTeX RDF
20	Letícia Rodrigues Bueno, Lucia Draque Penso, Fábio Protti, Victor R. Ramos, Dieter Rautenbach, Uéverton S. Souza	On the hardness of finding the geodetic number of a subcubic graph.	Inf. Process. Lett.	2018	DBLP DOI BibTeX RDF