Search results for "bounded-degree"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
72	Lap Chi Lau, Mohit Singh	Additive approximation for bounded degree survivable network design.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms, steiner tree, bounded degree, iterative rounding, survivable network design
65	Yu Wang 0003, Xiang-Yang Li 0001	Localized construction of bounded degree and planar spanner for wireless ad hoc networks.	DIALM-POMC	2003	DBLP DOI BibTeX RDF	wireless ad hoc networks, topology control, localized algorithm, spanner, planar, bounded degree
59	Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung	Degree Bounded Network Design with Metric Costs.	FOCS	2008	DBLP DOI BibTeX RDF
58	Franz-Josef Brandenburg	The Equivalence of Boundary and Confluent Graph Grammars on Graph Languages of Bounded Degree.	RTA	1991	DBLP DOI BibTeX RDF	boundary and confluent graph grammars, operator normal form, graph languages of bounded degree, graph grammars
57	Mohit Singh, Lap Chi Lau	Approximating minimum bounded degree spanning trees to within one of optimal.	STOC	2007	DBLP DOI BibTeX RDF	approximation algorithm, spanning trees, bounded degree, iterative rounding
56	Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, Dror Rawitz	Resource Allocation in Bounded Degree Trees.	Algorithmica	2009	DBLP DOI BibTeX RDF	Bounded degree trees, Scheduling, Approximation algorithms, Bandwidth allocation, Storage allocation
52	Paola Alimonti, Tiziana Calamoneri	Improved Approximations of Independent Dominating Set in Bounded Degree Graphs.	WG	1996	DBLP DOI BibTeX RDF	Minimum Independent Dominating Set, Approximation Algorithms, Local Search, Greedy, Regular Graphs, Cubic Graphs, Bounded Degree Graphs
50	Roy Friedman, Alex Kogan	Brief announcement: deterministic dominating set construction in networks with bounded degree.	PODC	2010	DBLP DOI BibTeX RDF	dominating sets, bounded degree graphs, distributed approximation algorithms
50	Yu Wang 0003, Xiang-Yang Li 0001	Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks.	Mob. Networks Appl.	2006	DBLP DOI BibTeX RDF	Wireless ad hoc networks, topology control, localized algorithm, spanner, planar, bounded degree
50	Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid	Constructing Plane Spanners of Bounded Degree and Low Weight.	Algorithmica	2005	DBLP DOI BibTeX RDF	Low weight graphs, Computational geometry, Planar graphs, Spanners, Bounded degree graphs
49	Artur Czumaj, Christian Sohler	On testable properties in bounded degree graphs.	SODA	2007	DBLP BibTeX RDF
48	Gruia Calinescu, Cristina G. Fernandes, Bruce A. Reed	Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width.	IPCO	1998	DBLP DOI BibTeX RDF
46	Prosenjit Bose, Vida Dujmovic, David R. Wood	Induced Subgraphs of Bounded Degree and Bounded Treewidth.	WG	2005	DBLP DOI BibTeX RDF
46	Stefan S. Dantchev, Florent R. Madelaine	Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems.	CSR	2006	DBLP DOI BibTeX RDF	Constraint Satisfaction, Duality, Monadic Second Order Logic, Logic in Computer Science, Graph Homomorphism
45	Christos Kaklamanis, Danny Krizanc, Satish Rao	Universal Emulations with Sublogarithmic Slowdown	FOCS	1993	DBLP DOI BibTeX RDF	arbitrary bounded degree networks, universal emulations, sublogarithmic slowdown, bounded degree networks, area-universal network, VLSI layout area, N-node network, sublogarithmic bounds, hypercube, butterfly
42	Tamás Király, Lap Chi Lau, Mohit Singh	Degree Bounded Matroids and Submodular Flows.	IPCO	2008	DBLP DOI BibTeX RDF
37	Hussein M. Alnuweiri	A New Class of Optimal Bounded-Degree VLSI Sorting Networks.	IEEE Trans. Computers	1993	DBLP DOI BibTeX RDF	VLSI sorting networks, optimal VLSI sorters, rotate-sort, enumeration-sort, reduced-area, K-shuffle layouts, VLSI, optimisation, logic design, sorting, time complexity, bounded-degree
37	Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman	On the Fault Tolerance of Some Popular Bounded-Degree Networks	FOCS	1992	DBLP DOI BibTeX RDF	bounded-degree networks, worst-case faults, shuffle-exchange graph, constant-factor slowdown, routing packets, fault tolerance, parallel computation, hypercubic networks, binary trees, meshes of trees
37	Kieran T. Herley	Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version)	FOCS	1989	DBLP DOI BibTeX RDF	small shared memories, bounded degree networks, PRAM algorithms, simulation, parallel random-access machine, PRAM
37	Sunil Arya, Michiel H. M. Smid	Efficient Construction of a Bounded Degree Spanner with Low Weight.	ESA	1994	DBLP DOI BibTeX RDF
36	Xiang-Yang Li 0001, Yu Wang 0003	Efficient Construction of Low Weight Bounded Degree Planar Spanner.	COCOON	2003	DBLP DOI BibTeX RDF
34	Iyad A. Kanj, Ljubomir Perkovic	Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks.	ALGOSENSORS	2006	DBLP DOI BibTeX RDF
33	Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto	The Travelling Salesman Problem in Bounded Degree Graphs.	ICALP (1)	2008	DBLP DOI BibTeX RDF
33	Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, Dror Rawitz	Resource Allocation in Bounded Degree Trees.	ESA	2006	DBLP DOI BibTeX RDF
33	Markus Lohrey	Automatic Structures of Bounded Degree.	LPAR	2003	DBLP DOI BibTeX RDF
33	Oded Goldreich 0001, Dana Ron	Property Testing in Bounded Degree Graphs.	Algorithmica	2002	DBLP DOI BibTeX RDF	Approximation algorithms, Randomized algorithms, Graph algorithms, Property testing
33	Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender	A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth.	ESA	2001	DBLP DOI BibTeX RDF
33	Haim Kaplan, Ron Shamir	Bounded Degree Interval Sandwich Problems.	Algorithmica	1999	DBLP DOI BibTeX RDF	Parametrized complexity, Computational biology, Interval graphs, Design and analysis of algorithms
32	Sharon Marko, Dana Ron	Approximating the distance to properties in bounded-degree and general sparse graphs.	ACM Trans. Algorithms	2009	DBLP DOI BibTeX RDF	Sublinear approximation algorithms, property testing, graph properties, distance approximation
32	Renato M. Capocelli, Luisa Gargano, Ugo Vaccaro	Time Bound for Broadcasting in Bounded Degree Graphs.	WG	1989	DBLP DOI BibTeX RDF
32	Itai Benjamini, Oded Schramm, Asaf Shapira	Every minor-closed property of sparse graphs is testable.	STOC	2008	DBLP DOI BibTeX RDF	minor closed properties, graph algorithms, property testing
31	Luca Trevisan	Non-approximability results for optimization problems on bounded degree instances.	STOC	2001	DBLP DOI BibTeX RDF
30	Artur Czumaj, Christian Sohler	Testing Expansion in Bounded-Degree Graphs.	FOCS	2007	DBLP DOI BibTeX RDF
30	Osamu Maruyama, Satoru Miyano	Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete.	MFCS	1995	DBLP DOI BibTeX RDF
29	Uros Cibej, Aaron Li, István Miklós, Sohaib Nasir, Varun Srikanth	Constructing bounded degree graphs with prescribed degree and neighbor degree sequences.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
29	Uros Cibej, Aaron Li, István Miklós, Sohaib Nasir, Varun Srikanth	Constructing bounded degree graphs with prescribed degree and neighbor degree sequences.	CoRR	2021	DBLP BibTeX RDF
29	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Nash equilibria in graphical games on trees revisited.	EC	2006	DBLP DOI BibTeX RDF	PPAD-completeness, nash equilibrium, graphical games
29	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of edge dominating set problems.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	Minimum edge dominating set, Minimum maximal matching, Approximation lower bound, Everywhere dense graphs, Bounded degree graphs
29	Wai-Kei Mak, D. F. Wong 0001	Board-level multi-terminal net routing for FPGA-based logic emulation.	ICCAD	1995	DBLP DOI BibTeX RDF	board-level routing, bounded-degree hypergraph-to-graph transformation, logic emulation systems, multi-terminal net decomposition net, FPGA
28	Stratis Ioannidis, Christos Nomikos, Aris Pagourtzis, Stathis Zachos	Routing and Wavelength Assignment in Generalized WDM Tree Networks of Bounded Degree.	Panhellenic Conference on Informatics	2005	DBLP DOI BibTeX RDF	routing and path coloring, optical networking, wavelength assignment, WDM networks
28	Jaroslav Nesetril, Patrice Ossona de Mendez	Linear time low tree-width partitions and algorithmic consequences.	STOC	2006	DBLP DOI BibTeX RDF	bounded expansion, fraternal augmentation, coloration, first order logic, subgraph isomorphism, tree-width, graph minor
28	Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, Dimitrios M. Thilikos	Isomorphism for Graphs of Bounded Distance Width.	Algorithmica	1999	DBLP DOI BibTeX RDF	Distance pathwidth, Distance treewidth, Graph isomorphism, Fixed parameter tractability
27	Mohammad Khairul Hasan, Sung-Eui Yoon, Kyung-Yong Chwa	Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs.	FAW	2009	DBLP DOI BibTeX RDF
27	Dietrich Kuske, Markus Lohrey	Automatic Structures of Bounded Degree Revisited.	CSL	2009	DBLP DOI BibTeX RDF
27	Vadim V. Lozin, Martin Milanic	Tree-Width and Optimization in Bounded Degree Graphs.	WG	2007	DBLP DOI BibTeX RDF	Hereditary class of graphs, Induced Matching, Dominating set, Tree-width
27	Andrej Bogdanov, Kenji Obata, Luca Trevisan	A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.	FOCS	2002	DBLP DOI BibTeX RDF
27	Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid	Constructing Plane Spanners of Bounded Degree and Low Weight.	ESA	2002	DBLP DOI BibTeX RDF
27	Douglas Comer	Extracting unique rows of a bounded degree array using tries.	AFIPS National Computer Conference	1980	DBLP DOI BibTeX RDF
27	Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, Dimitrios M. Thilikos	Isomorphism for Graphs of Bounded Distance Width.	CIAC	1997	DBLP DOI BibTeX RDF
27	Iyad A. Kanj, Ljubomir Perkovic, Ge Xia	Computing Lightweight Spanners Locally.	DISC	2008	DBLP DOI BibTeX RDF
26	Peter Damaschke	Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms.	IWPEC	2009	DBLP DOI BibTeX RDF
26	Satyen Kale, C. Seshadhri 0001	An Expansion Tester for Bounded Degree Graphs.	ICALP (1)	2008	DBLP DOI BibTeX RDF
26	Sharon Marko, Dana Ron	Distance Approximation in Bounded-Degree and General Sparse Graphs.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
24	Oded Goldreich 0001, Dana Ron	A Sublinear Bipartiteness Tester for Bounded Degree Graphs.	Comb.	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 68Q25, 68R10
24	Mohammad Taghi Hajiaghayi, Naomi Nishimura	Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth.	MFCS	2002	DBLP DOI BibTeX RDF
24	Xavier Muñoz, Ignasi Sau	Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph.	WG	2008	DBLP DOI BibTeX RDF	SONET over WDM, bridgeless graph, optical networks, graph decomposition, traffic grooming, ADM, cubic graph
24	Michael R. Capalbo	Explicit Bounded-Degree Unique-Neighbor Concentrators.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C35
24	Therese C. Biedl, Dana F. Wilkinson	Bounded-Degree Independent Sets in Planar Graphs.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
24	Timothy M. Chan	Euclidean Bounded-Degree Spanning Tree Ratios.	Discret. Comput. Geom.	2004	DBLP DOI BibTeX RDF
24	Timothy M. Chan	Euclidean bounded-degree spanning tree ratios.	SCG	2003	DBLP DOI BibTeX RDF	approximation, minimum spanning trees, discrete geometry
24	Therese C. Biedl, Dana F. Wilkinson	Bounded-Degree Independent Sets in Planar Graphs.	ISAAC	2002	DBLP DOI BibTeX RDF
24	Marek Karpinski	Approximating Bounded Degree Instances of NP-Hard Problems.	FCT	2001	DBLP DOI BibTeX RDF
23	Andrea Francke, Michael Hoffmann 0001	The Euclidean degree-4 minimum spanning tree problem is NP-hard.	SCG	2009	DBLP DOI BibTeX RDF	degree-constricted graphs, degree-restricted graphs, np-complete, reduction, spanning trees, geometric optimization, geometric graphs, bounded-degree graphs
23	Juan A. Garay, Rafail Ostrovsky	Almost-Everywhere Secure Computation.	EUROCRYPT	2008	DBLP DOI BibTeX RDF	secure message transmission, almost-everywhere agreement, bounded-degree networks, Secure multi-party computation, expander graphs
23	Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh	Survivable network design with degree or order constraints.	STOC	2007	DBLP DOI BibTeX RDF	approximation algorithms, network design, NP-hard problems, bounded degree, iterative rounding
23	Wen-Zhan Song 0001, Yu Wang 0003, Xiang-Yang Li 0001, Ophir Frieder	Localized Algorithms for Energy Efficient Topology in Wireless Ad Hoc Networks.	Mob. Networks Appl.	2005	DBLP DOI BibTeX RDF	efficient localized algorithm, wireless ad hoc networks, topology control, spanner, planar, bounded degree, power assignment
23	Michael Hoffmann 0001, Csaba D. Tóth	Pointed and colored binary encompassing trees.	SCG	2005	DBLP DOI BibTeX RDF	spanning tree, line segments, bounded degree, pseudo-triangulation
23	Wen-Zhan Song 0001, Yu Wang 0003, Xiang-Yang Li 0001	Localized algorithms for energy efficient topology in wireless ad hoc networks.	MobiHoc	2004	DBLP DOI BibTeX RDF	wireless ad hoc networks, topology control, spanner, planar, bounded degree
23	Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio	On the Applications of Multiplicity Automata in Learning.	FOCS	1996	DBLP DOI BibTeX RDF	multiplicity automata, DNF formulae learnability, minimal multiplicity automaton, multiplicity automata learning, finite field polynomials, infinite field bounded-degree polynomials, decision trees, states, matrix, automata theory, automata theory, query complexity
23	Daniel A. Spielman, Shang-Hua Teng	Spectral Partitioning Works: Planar Graphs and Finite Element Meshes.	FOCS	1996	DBLP DOI BibTeX RDF	bounded-degree planar graphs, planar graphs, finite element analysis, numerical algorithms, spectral partitioning, finite element meshes
23	Nader H. Bshouty, Yishay Mansour	Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.	FOCS	1995	DBLP DOI BibTeX RDF	constant bounded product distribution, /spl epsiv/-approximation, j-disjoint DNF, bounded term size, learning (artificial intelligence), decision trees, interpolation, interpolation, finite fields, polynomials, decision theory, learning algorithms, learnability, multivariate polynomials, membership queries, bounded degree
23	Edwin Hsing-Mean Sha, Kenneth Steiglitz	Reconfigurability and Reliability of Systolic/Wavefront Arrays.	IEEE Trans. Computers	1993	DBLP DOI BibTeX RDF	wavefront arrays, fault-tolerant redundant structures, reliable arrays, application graph, finitely reconfigurable, locally reconfigurable, reliability, lower bound, fault tolerant computing, reconfigurability, time complexity, systolic arrays, systolic arrays, reconfigurable architectures, dynamic graphs, bounded-degree graphs
22	Sriram Sankaranarayanan 0001	Automatic invariant generation for hybrid systems using ideal fixed points.	HSCC	2010	DBLP DOI BibTeX RDF	verification, hybrid systems, invariants, conservation laws, algebraic geometry
22	Michael Colón	Approximating the Algebraic Relational Semantics of Imperative Programs.	SAS	2004	DBLP DOI BibTeX RDF
22	Oded Goldreich 0001, Laliv Tauber	Testing in the bounded-degree graph model with degree bound two.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
22	Christian Joseph Altomare	A semigroup proof of the bounded degree case of S.B. Raoʼs Conjecture on degree sequences and a bipartite analogue.	J. Comb. Theory, Ser. B	2012	DBLP DOI BibTeX RDF
22	Claus Diem	An Index Calculus Algorithm for Plane Curves of Small Degree.	ANTS	2006	DBLP DOI BibTeX RDF
22	Tatsuya Akutsu, Avraham A. Melkman, Takeyuki Tamura	Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree.	Int. J. Found. Comput. Sci.	2020	DBLP DOI BibTeX RDF
22	Vida Dujmovic, Pat Morin, David R. Wood	Queue Layouts of Graphs with Bounded Degree and Bounded Genus.	CoRR	2019	DBLP BibTeX RDF
22	Michael A. Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Torsten Ueckerdt	Planar Graphs of Bounded Degree Have Bounded Queue Number.	SIAM J. Comput.	2019	DBLP DOI BibTeX RDF
22	Alessio Conte, Mamadou Moustapha Kanté, Andrea Marino 0001, Takeaki Uno	Maximal Irredundant Set Enumeration in Bounded-Degeneracy and Bounded-Degree Hypergraphs.	IWOCA	2019	DBLP DOI BibTeX RDF
22	Benoît Darties, Rodolphe Giroudeau, Jean-Claude König, Valentin Pollet	The Balanced Connected Subgraph Problem: Complexity Results in Bounded-Degree and Bounded-Diameter Graphs.	COCOA	2019	DBLP DOI BibTeX RDF
22	Michael A. Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Torsten Ueckerdt	Planar graphs of bounded degree have bounded queue number.	STOC	2019	DBLP DOI BibTeX RDF
22	Steven Chaplick, Jirí Fiala 0001, Pim van 't Hof, Daniël Paulusma, Marek Tesar 0001	Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree.	Theor. Comput. Sci.	2015	DBLP DOI BibTeX RDF
22	Steven Chaplick, Jirí Fiala 0001, Pim van 't Hof, Daniël Paulusma, Marek Tesar 0001	Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree.	CoRR	2014	DBLP BibTeX RDF
22	Kord Eickmeyer, Ken-ichi Kawarabayashi	Approximating Multi Commodity Network Design on Graphs of Bounded Pathwidth and Bounded Degree.	SAGT	2013	DBLP DOI BibTeX RDF
22	Steven Chaplick, Jirí Fiala 0001, Pim van 't Hof, Daniël Paulusma, Marek Tesar 0001	Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree.	FCT	2013	DBLP DOI BibTeX RDF
22	Albert Atserias	The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs.	SAT	2013	DBLP DOI BibTeX RDF
22	Satyajit Banerjee, Atish Datta Chowdhury, Subhas Kumar Ghosh	Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs.	Inf. Process. Lett.	2009	DBLP DOI BibTeX RDF
22	Prosenjit Bose, Vida Dujmovic, David R. Wood	Induced Subgraphs of Bounded Degree and Bounded Treewidth.	Contributions Discret. Math.	2006	DBLP BibTeX RDF
22	Gruia Calinescu, Cristina G. Fernandes, Bruce A. Reed	Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width.	J. Algorithms	2003	DBLP DOI BibTeX RDF
22	Gruia Calinescu, Cristina G. Fernandes	Multicuts in Unweighted Digraphs with Bounded Degree and Bounded Tree-Width.	Electron. Notes Discret. Math.	2001	DBLP DOI BibTeX RDF
22	Ganeshkumar Ganapathysaravanabavan, Tandy J. Warnow	Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time.	WABI	2001	DBLP DOI BibTeX RDF
22	Edward R. Scheinerman, Ann N. Trenk	On Generalized Perfect Graphs: Bounded Degree and Bounded Edge Perfection.	Discret. Appl. Math.	1993	DBLP DOI BibTeX RDF
21	Martin Fürer, Shiva Prasad Kasiviswanathan	Approximately Counting Embeddings into Random Graphs.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
21	Arist Kojevnikov, Alexander S. Kulikov	Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.	SAT	2006	DBLP DOI BibTeX RDF
21	Michael Dom, Jiong Guo, Rolf Niedermeier	Bounded Degree Closest k-Tree Power Is NP-Complete.	COCOON	2005	DBLP DOI BibTeX RDF
21	Michal Malafiejski, Krzysztof Giaro, Robert Janczewski, Marek Kubale	Sum Coloring of Bipartite Graphs with Bounded Degree.	Algorithmica	2004	DBLP DOI BibTeX RDF	Sum coloring, Chromatic sum, Bipartite graphs
21	Andreas Goerdt	The Cutting Plane Proof System with Bounded Degree of Falsity.	CSL	1991	DBLP DOI BibTeX RDF
20	Arnaud Carayol, Antoine Meyer	Linearly bounded infinite graphs.	Acta Informatica	2006	DBLP DOI BibTeX RDF